Back to Search
Start Over
Finding a maximum-weight induced -partite subgraph of an -triangulated graph
- Source :
-
Discrete Applied Mathematics . Apr2010, Vol. 158 Issue 7, p765-770. 6p. - Publication Year :
- 2010
-
Abstract
- Abstract: An -triangulated graph is a graph in which every odd cycle has two non-crossing chords; -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 -partite subgraph of an -triangulated graph, and show that the problem of finding a maximum-size bipartite induced subgraph in a clique-separable graph is -complete. [Copyright &y& Elsevier]
Details
- Language :
- English
- ISSN :
- 0166218X
- Volume :
- 158
- Issue :
- 7
- Database :
- Academic Search Index
- Journal :
- Discrete Applied Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 48602117
- Full Text :
- https://doi.org/10.1016/j.dam.2008.08.020