| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 429052 | Information Processing Letters | 2011 | 4 Pages |
Abstract
We present a simple unified algorithmic process which uses either LexBFS or MCS on a chordal graph to generate the minimal separators and the maximal cliques in linear time in a single pass.
► We find all the maximal cliques and minimal separators of a chordal graph. ► We unify results on algorithms MCS and LexBFS. ► A single linear-time pass is sufficient. ► We use moplexes (a generalization simplicial vertices) to prove our results.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Anne Berry, Romain Pogorelcnik,