TY - JOUR

T1 - Lower bounds on the lengths of node sequences in directed graphs

AU - Markowsky, George

AU - Tarjan, Robert Endre

N1 - Funding Information:
* The Research of the second author was partially supported by National Science Foundation Grant GJ-35604XI, by a Miller Research Fellowship at University of California; and by National Science Foundation Grant DCR72-03752 A02 at Stanford University.

PY - 1976/12

Y1 - 1976/12

N2 - A strong node sequence for a directed graph G=(N,A) is a sequence of nodes containing every cycle-free path of G as a subsequence. A weak node sequence for G is a sequence of nodes containing every basic path in G as a subsequence, where a basic path n1, n2, ..., nk is a path from n1 to nk such that no proper subsequence is a path from n1 to nk. (Every strong node sequence for G is a weak node sequence for G.) Kennedy has developed a global program data flow analysis method using node sequences. Kwiatowski and Kleitman have shown that any strong node sequence for the complete graph on n nodes must have length at least n2-O(n7/4+α), for arbitrary positive ε. Every graph on n nodes has a strong sequence of length n2-2n+4, so this bound is tight to within O(n7/4+α). However, the complete graph on n nodes has a weak node sequence of length n nodes (all with in-degree and out-degree bounded by two) such that any weak node sequence for G has length at least 1/2 log2 n-O(n log log n). Aho and Ullman have shown that every reducible flow graph has a strong node sequence of length O(n log2 n); thus our bound is tight to within a constant factor for reducible graphs. We also show that for infinitely many n, there is a (non-reducible) flow graph H with n nodes (all with in-degree and out-degree bounded by two), such that any weak node sequence for H has length at least cn2, where c is a positive constant. This bound, too, is tight to within a constant factor.

AB - A strong node sequence for a directed graph G=(N,A) is a sequence of nodes containing every cycle-free path of G as a subsequence. A weak node sequence for G is a sequence of nodes containing every basic path in G as a subsequence, where a basic path n1, n2, ..., nk is a path from n1 to nk such that no proper subsequence is a path from n1 to nk. (Every strong node sequence for G is a weak node sequence for G.) Kennedy has developed a global program data flow analysis method using node sequences. Kwiatowski and Kleitman have shown that any strong node sequence for the complete graph on n nodes must have length at least n2-O(n7/4+α), for arbitrary positive ε. Every graph on n nodes has a strong sequence of length n2-2n+4, so this bound is tight to within O(n7/4+α). However, the complete graph on n nodes has a weak node sequence of length n nodes (all with in-degree and out-degree bounded by two) such that any weak node sequence for G has length at least 1/2 log2 n-O(n log log n). Aho and Ullman have shown that every reducible flow graph has a strong node sequence of length O(n log2 n); thus our bound is tight to within a constant factor for reducible graphs. We also show that for infinitely many n, there is a (non-reducible) flow graph H with n nodes (all with in-degree and out-degree bounded by two), such that any weak node sequence for H has length at least cn2, where c is a positive constant. This bound, too, is tight to within a constant factor.

UR - http://www.scopus.com/inward/record.url?scp=58149410937&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=58149410937&partnerID=8YFLogxK

U2 - 10.1016/S0012-365X(76)80007-6

DO - 10.1016/S0012-365X(76)80007-6

M3 - Article

AN - SCOPUS:58149410937

SN - 0012-365X

VL - 16

SP - 329

EP - 337

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 4

ER -