About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Discrete Mathematics
Paper
Lower bounds on the lengths of node sequences in directed graphs
Abstract
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. © 1976 North-Holland Publishing Company.