Tree-Width and Optimization in Bounded Degree Graphs

DOI10.1007/978-3-540-74839-7_5zbMath1141.68540OpenAlexW1559280168MaRDI QIDQ3508553

Martin Milanič, Vadim V. Lozin

Publication date: 1 July 2008

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-74839-7_5

zbMATH Keywords

Dominating setTree-widthHereditary class of graphsInduced Matching

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (1)

Graph classes with and without powers of bounded clique-width

Cites Work

• Unnamed Item
• Domination in convex and chordal bipartite graphs
• Some results on graphs without long induced paths
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• On maximal independent sets of vertices in claw-free graphs
• Treewidth for graphs with small chordality
• Independent domination in finitely defined classes of graphs
• On linear and circular structure of (claw, net)-free graphs
• Finding maximum induced matchings in subclasses of claw-free and \(P_5\)-free graphs, and in graphs with matching and induced matching of equal maximum size
• Chordal bipartite graphs of bounded tree- and clique-width
• On maximum induced matchings in bipartite graphs
• Upper bounds to the clique width of graphs
• New results on induced matchings
• Grad and classes with bounded expansion. I: Decompositions
• Line graphs of bounded clique-width
• NP-hard graph problems and boundary classes of graphs
• A characterization of graphs without long induced paths
• Edge Dominating Sets in Graphs
• On the diameter ofi-center in a graph without long induced paths
• On the complexity of domination number determination in monogenic classes of graphs
• On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree

This page was built for publication: Tree-Width and Optimization in Bounded Degree Graphs