Finding a maximum-weight induced k-partite subgraph of an i-triangulated graph

被引：15

作者：

Addario-Berry, Louigi ^{[1
]}

Kennedy, W. S. ^{[1
]}

King, Andrew D. ^{[1
]}

Li, Zhentao ^{[1
]}

Reed, Bruce ^{[1
]}

机构：

[1] McGill Univ, Sch Comp Sci, Montreal, PQ, Canada

来源：

DISCRETE APPLIED MATHEMATICS | 2010年 / 158卷 / 07期

关键词：

Graph algorithm; Clique-separable graph; i-triangulated graph; Tree decomposition; POLYTOPE; FACETS;

D O I：

10.1016/j.dam.2008.08.020

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

An i-triangulated graph is a graph in which every odd cycle has two non-crossing chords; i-triangulated graphs form a subfamily of perfect graphs. A slightly more general family of perfect graphs are clique-separable graphs. A graph is clique-separable precisely if every induced subgraph either has a clique cutset, or is a complete multipartite graph or a clique joined to an arbitrary bipartite graph. We exhibit a polynomial time algorithm for finding a maximum-weight induced k-partite subgraph of an i-triangulated graph, and show that the problem of finding a maximum-size bipartite induced subgraph in a clique-separable graph is NP-complete. (c) 2008 Elsevier B.V. All rights reserved.

引用

页码：765 / 770

页数：6

共 14 条

[1] FACETS OF THE BALANCED (ACYCLIC) INDUCED SUBGRAPH POLYTOPE [J].