Header menu link for other important links
X
Minimal vertex separators of chordal graphs
, Madhavan C.E.Veni
Published in Elsevier BV
1998
Volume: 89
   
Issue: 1-3
Pages: 155 - 168
Abstract

Chordal graphs form an important and widely studied subclass of perfect graphs. The set of minimal vertex separators constitute an unique class of separators of a chordal graph and capture the structure of the graph. In this paper, we explore the connection between perfect elimination orderings of a chordal graph and its minimal vertex separators. Specifically, we prove a characterization of these separators in terms of the monotone adjacency sets of the vertices of the graph, numbered by the maximum cardinality search (MCS) scheme. This leads to a simple linear-time algorithm to identify the minimal vertex separators of a chordal graph using the MCS scheme. We also introduce the notion of multiplicity of a minimal vertex separator which indicates the number of different pairs of vertices separated by it. We prove a useful property of the lexicographic breadth first scheme (LBFS) that enables us to determine the multiplicities of minimal vertex separators of a chordal graph.

About the journal
JournalData powered by TypesetDiscrete Applied Mathematics
PublisherData powered by TypesetElsevier BV
Open AccessNo