Optimization problems in multiple subtree graphs

DOI10.1016/j.dam.2010.03.010zbMath1213.05247OpenAlexW2112723368MaRDI QIDQ531599

Dror Rawitz, Danny Hermelin

Publication date: 19 April 2011

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

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

zbMATH Keywords

approximation algorithmsmaximum independent setmaximum cliqueminimum coloringminimum vertex coverminimum dominating setmultiple subtree graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

Optimization problems in dotted interval graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Recognizing graphs with fixed interval number is NP-complete
• Path hitting in acyclic graphs
• Efficient bounds for the stable set, vertex cover and set packing problems
• Optimization, approximation, and complexity classes
• Some simplified NP-complete graph problems
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• KKM -- a topological approach for trees
• Dominating Sets in Chordal Graphs
• Extremal Values of the Interval Number of a Graph
• A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
• Scheduling Split Intervals
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph