Tree-width, path-width, and cutwidth

DOI10.1016/0166-218X(93)90171-JzbMath0788.05057MaRDI QIDQ1801672

Nir Solel, Ephraim Korach

Publication date: 17 August 1993

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

decompositioncutwidthtree-width

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (32)

Decomposability of a class of \(k\)-cutwidth critical graphs ⋮ Improved algorithms for some competitive location centroid problems on paths, trees and graphs ⋮ Submodular Unsplittable Flow on Trees ⋮ Metric Embedding via Shortest Path Decompositions ⋮ Characterizations of \(k\)-cutwidth critical trees ⋮ The Firefighter Problem: A Structural Analysis ⋮ Bounding threshold dimension: realizing graphic Boolean functions as the AND of majority gates ⋮ On the expressive power of CNF formulas of bounded tree- and clique-width ⋮ Strong SDP based bounds on the cutwidth of a graph ⋮ Edge-treewidth: algorithmic and combinatorial properties ⋮ Population-based iterated greedy algorithm for the S-labeling problem ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On 3-cutwidth critical graphs ⋮ An Upper Bound for Resolution Size: Characterization of Tractable SAT Instances ⋮ Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth ⋮ Subset Glauber dynamics on graphs, hypergraphs and matroids of bounded tree-width ⋮ Cutwidth: obstructions and algorithmic aspects ⋮ Large Angle Crossing Drawings of Planar Graphs in Subquadratic Area ⋮ The complexity of subgraph isomorphism for classes of partial k-trees ⋮ Computing the Chromatic Number Using Graph Decompositions via Matrix Rank ⋮ Neighbourhood-width of trees ⋮ The firefighter problem: further steps in understanding its complexity ⋮ The treewidth of line graphs ⋮ Fixed-parameter algorithms for protein similarity search under mRNA structure constraints ⋮ Submodular unsplittable flow on trees ⋮ On tseitin formulas, read-once branching programs and treewidth ⋮ Complete-subgraph-transversal-sets problem on bounded treewidth graphs ⋮ One-visibility cops and robber on trees: optimal cop-win strategies ⋮ Decompositions of critical trees with cutwidth \(k\) ⋮ Computing the chromatic number using graph decompositions via matrix rank ⋮ The treewidth of 2-section of hypergraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On minimizing width in linear layouts
• Graph minors. I. Excluding a forest
• Graphs with small bandwidth and cutwidth
• Graph minors. IV: Tree-width and well-quasi-ordering
• Polynomial Time Algorithms for the MIN CUT Problem on Degree Restricted Trees
• Graph minors. II. Algorithmic aspects of tree-width
• Complexity of Finding Embeddings in a k-Tree
• A polynomial algorithm for the min-cut linear arrangement of trees
• Upper and Lower Bounds on the Complexity of the Min-Cut Linear Arrangement Problem on Trees

This page was built for publication: Tree-width, path-width, and cutwidth