Cycle rank
Relevant topics on |
Graph connectivity |
---|
In graph theory, the cycle rank of a directed graph is a digraph connectivity measure proposed first by Eggan and Büchi (Eggan 1963). Intuitively, this concept measures how close a digraph is to a directed acyclic graph (DAG), in the sense that a DAG has cycle rank zero, while a
Definition
The cycle rank r(G) of a digraph G = (V, E) is inductively defined as follows:
- If G is acyclic, then r(G) = 0.
- If G is strongly connectedand E is nonempty, then
- where is the digraph resulting from deletion of vertex v and all edges beginning or ending at v.
- If G is not strongly connected, then r(G) is equal to the maximum cycle rank among all strongly connected components of G.
The tree-depth of an undirected graph has a very similar definition, using undirected connectivity and connected components in place of strong connectivity and strongly connected components.
History
Cycle rank was introduced by Eggan (1963) in the context of star height of regular languages. It was rediscovered by (Eisenstat & Liu 2005) as a generalization of undirected tree-depth, which had been developed beginning in the 1980s and applied to sparse matrix computations (Schreiber 1982).
Examples
The cycle rank of a directed acyclic graph is 0, while a complete digraph of order n with a
Computing the cycle rank
Computing the cycle rank is computationally hard:
Applications
Star height of regular languages
The first application of cycle rank was in
- a finite set of states Q
- a finite set of input symbolsΣ
- a set of labeled edges δ, referred to as transition relation: Q × (Σ ∪{ε}) × Q. Here ε denotes the empty word.
- an initial state q0 ∈ Q
- a set of states F distinguished as accepting states F ⊆ Q.
A word w ∈ Σ* is accepted by the ε-NFA if there exists a
When speaking of digraph properties of a nondeterministic finite automaton A with state set Q, we naturally address the digraph with vertex set Q induced by its transition relation. Now the theorem is stated as follows.
- Eggan's Theorem: The star height of a regular language L equals the minimum cycle rank among all nondeterministic finite automata with ε-moves accepting L.
Proofs of this theorem are given by Eggan (1963), and more recently by Sakarovitch (2009).
Cholesky factorization in sparse matrix computations
Another application of this concept lies in
See also
References
- Zbl 0818.68118.
- Dereniowski, Dariusz; Kubale, Marek (2004), "Cholesky Factorization of Matrices in Parallel and Ranking of Graphs", 5th International Conference on Parallel Processing and Applied Mathematics (PDF), Lecture Notes on Computer Science, vol. 3019, Springer-Verlag, pp. 985–992, Zbl 1128.68544, archived from the original(PDF) on 2011-07-16.
- Eggan, Lawrence C. (1963), "Transition graphs and the star-height of regular events", Zbl 0173.01504.
- Eisenstat, Stanley C.; Liu, Joseph W. H. (2005), "The theory of elimination trees for sparse unsymmetric matrices", SIAM Journal on Matrix Analysis and Applications, 26 (3): 686–705, .
- Gruber, Hermann (2012), "Digraph Complexity Measures and Applications in Formal Language Theory" (PDF), Discrete Mathematics & Theoretical Computer Science, 14 (2): 189–204.
- Gruber, Hermann; Holzer, Markus (2008), "Finite automata, digraph connectivity, and regular expression size" (PDF), .
- McNaughton, Robert (1969), "The loop complexity of regular events", Information Sciences, 1 (3): 305–328, .
- Rossman, Benjamin (2008), "Homomorphism preservation theorems", .
- Sakarovitch, Jacques (2009), Elements of Automata Theory, Cambridge University Press, ISBN 0-521-84425-8
- Schreiber, Robert (1982), "A new implementation of sparse Gaussian elimination" (PDF), doi:10.1145/356004.356006, archived from the original(PDF) on 2011-06-07, retrieved 2010-01-04.