Premium
One‐phase algorithm for the determination of minimal vertex separators of chordal graphs
Author(s) -
Markenzon Lilian,
Da Costa Pereira Paulo Renato
Publication year - 2010
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/j.1475-3995.2009.00751.x
Subject(s) - chordal graph , lexicographical order , vertex (graph theory) , interval graph , algorithm , treewidth , computer science , mathematics , maximal independent set , combinatorics , pathwidth , graph , 1 planar graph , line graph
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.