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

DOI10.1016/J.DAM.2008.08.020zbMATH Open1216.05152OpenAlexW2090354123MaRDI QIDQ972337FDOQ972337

Authors Louigi Addario-Berry, Zhentao Li, W. Sean Kennedy, Andrew D. King, Bruce Reed 

Publication date 25 May 2010

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2008.08.020

zbMATH Keywords

graph algorithmtree decomposition\(i\)-triangulated graphclique-separable graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• scientific article; zbMATH DE number 3999981
• Polyhedral results for the bipartite induced subgraph problem
• scientific article; zbMATH DE number 3908479
• On the Maximum Weight Clique Problem
• Optimizing weakly triangulated graphs

Cites work

• scientific article; zbMATH DE number 3889564 (Why is no real title available?)
• scientific article; zbMATH DE number 3908479 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1455118 (Why is no real title available?)
• scientific article; zbMATH DE number 1877046 (Why is no real title available?)
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Compositions of Graphs and Polyhedra I: Balanced Induced Subgraphs and Acyclic Subgraphs
• Facets of the Bipartite Subgraph Polytope
• Facets of the balanced (acyclic) induced subgraph polytope
• Graph Bipartization and via minimization
• Polyhedral results for the bipartite induced subgraph problem
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• The strong perfect graph theorem

Cited in

(12)

• On the Generalized $\vartheta$-Number and Related Problems for Highly Symmetric Graphs
• Reconfiguration of Colorable Sets in Classes of Perfect Graphs
• Maximum bipartite subgraphs of geometric intersection graphs
• New characterizations of Gallai's \(i\)-triangulated graphs
• Fair allocation of indivisible items with conflict graphs
• The Maximum k-Colorable Subgraph Problem and Related Problems
• Approximate minimum sum colorings and maximum \(k\)-colorable subgraphs of chordal graphs
• Reconfiguration of colorable sets in classes of perfect graphs
• Approximability of clique transversal in perfect graphs
• Contraction and deletion blockers for perfect graphs and \(H\)-free graphs
• Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs
• Inductive graph invariants and approximation algorithms

This page was built for publication: Finding a maximum-weight induced \(k\)-partite subgraph of an \(i\)-triangulated graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q972337)