Tree-Width and Optimization in Bounded Degree Graphs

DOI10.1007/978-3-540-74839-7_5MaRDI QIDQ3508553zbMATH OpenOpenAlexFDO

Authors Martin Milanič, Vadim 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) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree
• scientific article; zbMATH DE number 4210186
• Degree sequence optimization in bounded treewidth
• scientific article; zbMATH DE number 6783432
• Known algorithms on graphs of bounded treewidth are probably optimal

Cites work

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

Cited in

(18)

• Trimming weighted graphs of bounded treewidth
• Graph searching and a min-max theorem for tree-width
• Induced subgraphs of bounded degree and bounded treewidth
• scientific article; zbMATH DE number 2188361 (Why is no real title available?)
• Resource allocation in bounded degree trees
• Graph classes with and without powers of bounded clique-width
• Tree-width and circumference of graphs
• Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs
• Graph-Theoretic Concepts in Computer Science
• Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth
• scientific article; zbMATH DE number 2044920 (Why is no real title available?)
• Treewidth of display graphs: bounds, brambles and applications
• Degree sequence optimization in bounded treewidth
• Optimal parametric search on graphs of bounded tree-width
• Canonizing Graphs of Bounded Tree Width in Logspace
• Algorithms for graphs of bounded treewidth via orthogonal range searching
• Tree-edges deletion problems with bounded diameter obstruction sets
• scientific article; zbMATH DE number 6783432 (Why is no real title available?)

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

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