maxcard.search {lcd} | R Documentation |
Performs a maximum cardinality search on an undirected graph to determine whether it is triangulated.
maxcard.search(amat)
amat |
the adjacency matrix of the undirected graph. |
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. |
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.
Zongming Ma and Xiangrui Meng
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.