### 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 n_{1}, n_{2}, ..., n_{k} is a path from n_{1} to n_{k} such that no proper subsequence is a path from n_{1} to n_{k}. (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 n^{2}-O(n^{7/4+α}), for arbitrary positive ε. Every graph on n nodes has a strong sequence of length n^{2}-2n+4, so this bound is tight to within O(n^{7/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 log_{2} 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 log_{2 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 cn^{2}, where c is a positive constant. This bound, too, is tight to within a constant factor.

Original language | English (US) |
---|---|

Pages (from-to) | 329-337 |

Number of pages | 9 |

Journal | Discrete Mathematics |

Volume | 16 |

Issue number | 4 |

DOIs | |

State | Published - Dec 1976 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics

## Fingerprint Dive into the research topics of 'Lower bounds on the lengths of node sequences in directed graphs'. Together they form a unique fingerprint.

## Cite this

*Discrete Mathematics*,

*16*(4), 329-337. https://doi.org/10.1016/S0012-365X(76)80007-6