On Linear Recognition of Tree-Width at Most Four
From MaRDI portal
Publication:4875439
DOI10.1137/S0895480193243043zbMath0847.05087MaRDI 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 algorithm; NP-hard; linear time algorithm; tree-width; linear time complexity; \(k\)-elimination sequence; linear recognition
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
05C75: Structural characterization of families of graphs
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Constructive linear time algorithms for branchwidth, Minimum size tree-decompositions, Minimum size tree-decompositions, Connected search for a lazy robber, Fast partitioning \(l\)-apex graphs with applications to approximating maximum induced-subgraph problems, Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth, Three-connected graphs whose maximum nullity is at most three, An implementation of the iterative proportional fitting procedure by propagation trees., The structure of obstructions to treewidth and pathwidth, Surfaces, tree-width, clique-minors, and partitions, Approximation algorithms for classes of graphs excluding single-crossing graphs as minors, Fixed-Parameter Tractability of Treewidth and Pathwidth