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

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• The strong perfect graph theorem
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Title not available (Why is that?)
• Graph Bipartization and via minimization
• Title not available (Why is that?)
• Facets of the balanced (acyclic) induced subgraph polytope
• Facets of the Bipartite Subgraph Polytope
• Polyhedral results for the bipartite induced subgraph problem
• Compositions of Graphs and Polyhedra I: Balanced Induced Subgraphs and Acyclic Subgraphs
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (12)

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

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)