One‐phase algorithm for the determination of minimal vertex separators of chordal graphs
Lilian Markenzon, Paulo Renato da Costa Pereira · International Transactions in Operational Research · 2010
Abstract 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.