On Linear Recognition of Tree-Width at Most Four
From MaRDI portal
Publication:4875439
DOI10.1137/S0895480193243043zbMath0847.05087OpenAlexW2067514766MaRDI QIDQ4875439
Publication date: 29 September 1996
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0895480193243043
graph algorithmNP-hardlinear time algorithmtree-widthlinear time complexity\(k\)-elimination sequencelinear recognition
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (12)
The structure of obstructions to treewidth and pathwidth ⋮ Approximation algorithms for classes of graphs excluding single-crossing graphs as minors ⋮ Fast partitioning \(l\)-apex graphs with applications to approximating maximum induced-subgraph problems ⋮ Fixed-Parameter Tractability of Treewidth and Pathwidth ⋮ Constructive linear time algorithms for branchwidth ⋮ Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth ⋮ Connected search for a lazy robber ⋮ Minimum size tree-decompositions ⋮ Three-connected graphs whose maximum nullity is at most three ⋮ Minimum size tree-decompositions ⋮ Surfaces, tree-width, clique-minors, and partitions ⋮ An implementation of the iterative proportional fitting procedure by propagation trees.
This page was built for publication: On Linear Recognition of Tree-Width at Most Four
