On Linear Recognition of Tree-Width at Most Four

DOI10.1137/S0895480193243043zbMATH Open0847.05087OpenAlexW2067514766MaRDI QIDQ4875439FDOQ4875439

Authors: 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

Recommendations

• An efficient algorithm for determining whether a cubic graph is toroidal
• Obtaining a Planar Graph by Vertex Deletion
• The Computational Complexity of the Parallel Knock-Out Problem
• Minimal elimination ordering for graphs of bounded degree
• Recognizing quasi-triangulated graphs.
• Into the square: on the complexity of some quadratic-time solvable problems
• Efficient algorithms for solving systems of linear equations and path problems
• A characterization of linearizable instances of the quadratic minimum spanning tree problem
• A solvable case of quadratic 0-1 programming

zbMATH Keywords

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

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75)

Cited In (14)

• On the linear arboricity of graphs with treewidth at most four
• Constructive linear time algorithms for branchwidth
• Fixed-Parameter Tractability of Treewidth and Pathwidth
• Fast partitioning \(l\)-apex graphs with applications to approximating maximum induced-subgraph problems
• Three-connected graphs whose maximum nullity is at most three
• Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth
• Surfaces, tree-width, clique-minors, and partitions
• Minimum size tree-decompositions
• Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
• Snakes and Ladders: A Treewidth Story
• The structure of obstructions to treewidth and pathwidth
• Connected search for a lazy robber
• Minimum size tree-decompositions
• 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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4875439)