Maximum cardinality search
Maximum cardinality search is a simple ordering a vertices that is useful in determining the chordality of a graph.
max_cardinality(graph)
graph |
The input graph. It may be directed, but edge directions are ignored, as the algorithm is defined for undirected graphs. |
Maximum cardinality search visits the vertices in such an order that every time the vertex with the most already visited neighbors is visited. Ties are broken randomly.
The algorithm provides a simple basis for deciding whether a graph is
chordal, see References below, and also is_chordal.
A list with two components:
alpha |
Numeric vector. The vertices ordered according to the maximum cardinality search. |
alpham1 |
Numeric vector. The inverse of |
Gabor Csardi csardi.gabor@gmail.com
Robert E Tarjan and Mihalis Yannakakis. (1984). Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM Journal of Computation 13, 566–579.
## The examples from the Tarjan-Yannakakis paper
g1 <- graph_from_literal(A-B:C:I, B-A:C:D, C-A:B:E:H, D-B:E:F,
E-C:D:F:H, F-D:E:G, G-F:H, H-C:E:G:I,
I-A:H)
max_cardinality(g1)
is_chordal(g1, fillin=TRUE)
g2 <- graph_from_literal(A-B:E, B-A:E:F:D, C-E:D:G, D-B:F:E:C:G,
E-A:B:C:D:F, F-B:D:E, G-C:D:H:I, H-G:I:J,
I-G:H:J, J-H:I)
max_cardinality(g2)
is_chordal(g2, fillin=TRUE)Please choose more modern alternatives, such as Google Chrome or Mozilla Firefox.