 |
RUTCOR Colloquia - April 21, 2005
Speaker: Andreas Brandstädt
Affiliation: University of Rostock, Department of Computer Science
Title: On clique separators, nearly chordal graphs and the Maximum Weight Stable Set problem
Time: 1:30 - 2:30 PM
Location: RUTCOR Building - Room 139, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
Clique separators in graphs are a helpful
tool used by Tarjan as a divide-and-conquer approach
for solving various
graph problems such as the Maximum Weight Stable Set
(MWS) Problem, Maximum Clique, Graph Coloring and
Minimum Fill-in but
few examples of graph classes having clique
separators are known. We use this method to solve
MWS in polynomial time for
two classes where the unweighted Maximum Stable Set
(MS) Problem is solvable in polynomial time by
augmenting techniques
but the complexity of the MWS problem was open. We
also combine clique separators with decomposition by
homogeneous sets
in graphs and use the following notion:
A graph is nearly π if for each of its
vertices, the subgraph induced by the set of its
nonneighbors has
property π. We deal with the cases π ∈
{chordal, perfect}. This also simplifies a
result obtained by
struction.
Back to Seminars Page.
Back to RUTCOR homepage.
|
