Optimization problems in multiple subtree graphs

DOI10.1016/J.DAM.2010.03.010MaRDI QIDQ531599zbMATH OpenOpenAlexFDO

Authors Danny Hermelin, Dror Rawitz

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

maximum cliqueapproximation algorithmsmaximum independent setminimum coloringminimum vertex coverminimum dominating setmultiple subtree graphs

Mathematics Subject Classification ID

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

Recommendations

• Optimization problems in multiple subtree graphs
• Optimizing constrained subtrees of trees
• Optimization problems in multiple-interval graphs
• Optimization problems in multiple-interval graphs
• Publication:4733693
• The maximum utilization subtree problem
• Optimization problems in multicast tree construction
• On spanning tree problems with multiple objectives
• scientific article; zbMATH DE number 1210933

Cites work

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

Cited in

(5)

• Optimization problems in dotted interval graphs
• Optimization problems in multiple subtree graphs
• Approximating the minimum clique cover and other hard problems in subtree filament graphs
• Optimization problems in multiple-interval graphs
• The Multi-Tier Tree Problem

This page was built for publication: Optimization problems in multiple subtree graphs

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