igraph (version 0.6-1)

maximum.cardinality.search: Maximum cardinality search

Description

Maximum cardinality search is a simple ordering a vertices that is useful in determining the chordality of a graph.

Usage

maximum.cardinality.search(graph)

Arguments

graph
The input graph. It may be directed, but edge directions are ignored, as the algorithm is defined for undirected graphs.

Value

  • A list with two components:
  • alphaNumeric vector. The vertices ordered according to the maximum cardinality search.
  • alpham1Numeric vector. The inverse of alpha.

concept

  • maximum cardinality search
  • graph decomposition
  • chordal graph

Details

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.

References

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.

See Also

is.chordal

Examples

Run this code
## The examples from the Tarjan-Yannakakis paper
g1 <- graph.formula(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)
maximum.cardinality.search(g1)
is.chordal(g1, fillin=TRUE)

g2 <- graph.formula(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)
maximum.cardinality.search(g2)
is.chordal(g2, fillin=TRUE)

Run the code above in your browser using DataCamp Workspace