maxcard.search {lcd}R Documentation

Maximum cardinality search

Description

Performs a maximum cardinality search on an undirected graph to determine whether it is triangulated.

Usage

maxcard.search(amat)

Arguments

amat the adjacency matrix of the undirected graph.

Value

is.triangulated a logical value indicating whether the input graph is triangulated or not.
perfect.numbering a perfect numbering of the vertices.
card number of unlabeled neighbors when labeling each variable, with order compatible to the perfect numbering.
pi.record a record of unlabeled neighbors during the execution of the algorithm.

Note

Only the is.triangulated and perfect.numbering are supposed to be of interest to the users. The other two output components are mainly for track purpose.

Author(s)

Zongming Ma and Xiangrui Meng

References

Tarjan, R. E. and Yannakakis, M. (1984). Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM Journal on Computing, 13, 566-79.


[Package lcd version 0.7-2 Index]