# maximum.cardinality.search

From igraph v0.6.5-2
by Gabor Csardi

##### Maximum cardinality search

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

- Keywords
- graphs

##### 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.

##### 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`

.

##### Value

- A list with two components:
alpha Numeric vector. The vertices ordered according to the maximum cardinality search. alpham1 Numeric vector. The inverse of `alpha`

.

##### concept

- maximum cardinality search
- graph decomposition
- chordal graph

##### 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

##### Examples

```
## 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)
```

*Documentation reproduced from package igraph, version 0.6.5-2, License: GPL (>= 2)*

### Community examples

Looks like there are no examples yet.