| Article ID: | iaor20107459 |
| Volume: | 17 |
| Issue: | 6 |
| Start Page Number: | 683 |
| End Page Number: | 690 |
| Publication Date: | Nov 2010 |
| Journal: | International Transactions in Operational Research |
| Authors: | Markenzon Lilian, da Costa Pereira Paulo Renato |
The set of minimal vertex separators of chordal graphs is usually obtained by two-phase algorithms. Based on properties of the lexicographic breadth-first search, we propose a new one-phase algorithm. We present also a characterization for planar chordal graphs; using our proposed algorithm as an initial step, the implementation of the recognition algorithm becomes trivial.