Optimization problems in multiple subtree graphs

DOI10.1016/J.DAM.2010.03.010zbMATH Open1213.05247OpenAlexW2112723368MaRDI QIDQ531599FDOQ531599

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

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

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)

Cites Work

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

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)