Maximum cardinality search is a simple ordering a vertices that is useful in determining the chordality of a 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
A list with two components:
Numeric vector. The 1-based rank of each vertex in the graph such that the vertex with rank 1 is visited first, the vertex with rank 2 is visited second and so on.
Numeric vector. The inverse of
Gabor Csardi firstname.lastname@example.org
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)
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.