On Linear Recognition of Tree-Width at Most Four

DOI10.1137/S0895480193243043zbMath0847.05087MaRDI QIDQ4875439

Daniel P. Sanders

Publication date: 29 September 1996

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

graph algorithm; NP-hard; linear time algorithm; tree-width; linear time complexity; \(k\)-elimination sequence; linear recognition

Mathematics Subject Classification ID

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

Minimum size tree-decompositions, Minimum size tree-decompositions, 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