Tree-Width and Optimization in Bounded Degree Graphs
DOI10.1007/978-3-540-74839-7_5zbMATH Open1141.68540OpenAlexW1559280168MaRDI QIDQ3508553FDOQ3508553
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
Recommendations
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)
Cites Work
- Treewidth for graphs with small chordality
- Upper bounds to the clique width of graphs
- Grad and classes with bounded expansion. I: Decompositions
- NP-hard graph problems and boundary classes of graphs
- On the complexity of domination number determination in monogenic classes of graphs
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Some results on graphs without long induced paths
- On maximal independent sets of vertices in claw-free graphs
- On maximum induced matchings in bipartite graphs
- 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
- New results on induced matchings
- On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree
- Line graphs of bounded clique-width
- Independent domination in finitely defined classes of graphs
- Chordal bipartite graphs of bounded tree- and clique-width
- The tree- and clique-width of bipartite graphs in special classes
- A characterization of graphs without long induced paths
- On linear and circular structure of (claw, net)-free graphs
- On the diameter ofi-center in a graph without long induced paths
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
- Title not available (Why is that?)
- Resource allocation in bounded degree trees
- Tree-width and circumference of graphs
- Graph classes with and without powers of bounded clique-width
- Graph-Theoretic Concepts in Computer Science
- Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs
- Title not available (Why is that?)
- Treewidth of display graphs: bounds, brambles and applications
- Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth
- 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
- Title not available (Why is that?)
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)
