On Linear Recognition of Tree-Width at Most Four

DOI10.1137/S0895480193243043zbMath0847.05087OpenAlexW2067514766MaRDI QIDQ4875439

Daniel P. Sanders

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

zbMATH Keywords

graph algorithmNP-hardlinear time algorithmtree-widthlinear time complexity\(k\)-elimination sequencelinear recognition

Mathematics Subject Classification ID

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