Obstruction set isolation for the gate matrix layout problem

DOI10.1016/0166-218X(94)90021-3zbMath0941.68590OpenAlexW1973324808MaRDI QIDQ1336625

Michael A. Langston, Nancy G. Kinnersley

Publication date: 1 August 2000

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(94)90021-3

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (30)

The structure of obstructions to treewidth and pathwidth ⋮ Contraction obstructions for connected graph searching ⋮ Posets with cover graph of pathwidth two have bounded dimension ⋮ Obstructions to within a few vertices or edges of acyclic ⋮ Fixed-Parameter Tractability, A Prehistory, ⋮ Variable neighborhood search for the vertex separation problem ⋮ Characterizing width two for variants of treewidth ⋮ Sparse obstructions for minor-covering parameters ⋮ Characterizing graphs of maximum matching width at most 2 ⋮ Characterising graphs with no subdivision of a wheel of bounded diameter ⋮ \(k\)-apices of minor-closed graph classes. I: Bounding the obstructions ⋮ Order Reconfiguration under Width Constraints ⋮ Connected search for a lazy robber ⋮ On strict brambles ⋮ A lower bound for treewidth and its consequences ⋮ Obstructions for linear rank-width at most 1 ⋮ Forbidden directed minors and Kelly-width ⋮ A technique for recognizing graphs of bounded treewidth with application to subclasses of partial 2-paths ⋮ Four-searchable biconnected outerplanar graphs ⋮ On the geometric Ramsey number of outerplanar graphs ⋮ Characterization of graphs and digraphs with small process numbers ⋮ A Quartic Kernel for Pathwidth-One Vertex Deletion ⋮ Tree-decompositions of small pathwidth ⋮ Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2 ⋮ Independent-set reconfiguration thresholds of hereditary graph classes ⋮ Minor obstructions for apex-pseudoforests ⋮ A partial k-arboretum of graphs with bounded treewidth ⋮ Comparing linear width parameters for directed graphs ⋮ On computing graph minor obstruction sets ⋮ Algorithms and obstructions for linear-width and related search parameters

Cites Work

• Unnamed Item
• Graph minors. XX: Wagner's conjecture
• Graph minors. I. Excluding a forest
• Graph minors. V. Excluding a planar graph
• Nonconstructive advances in polynomial-time complexity
• Parallel concepts in graph theory
• The vertex separation and search number of a graph
• Graph minors. XIII: The disjoint paths problem
• Nonconstructive tools for proving polynomial-time decidability
• On Well-Partial-Order Theory and Its Application to Combinatorial Problems of VLSI Design
• Polynomial-time self-reducibility: theoretical motivations and practical results^∗

This page was built for publication: Obstruction set isolation for the gate matrix layout problem