On Well-Partial-Order Theory and Its Application to Combinatorial Problems of VLSI Design

DOI10.1137/0405010zbMath0739.68042OpenAlexW2036263637MaRDI QIDQ3989017

Michael A. Langston, Michael R. Fellows

Publication date: 28 June 1992

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

Full work available at URL: https://doi.org/10.1137/0405010

zbMATH Keywords

VLSIpolynomial-time complexitynonconstructive proofswell-partially- ordered sets

Mathematics Subject Classification ID

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

Related Items

Improved self-reduction algorithms for graphs with bounded treewidth, Obstruction set isolation for the gate matrix layout problem, A MATHEMATICAL COMMITMENT WITHOUT COMPUTATIONAL STRENGTH, Approximating the pathwidth of outerplanar graphs, On search, decision, and the efficiency of polynomial-time algorithms, Fixed-Parameter Tractability, A Prehistory,, Fixed-Parameter Tractability of Treewidth and Pathwidth, Parameterized complexity of graph burning, On algorithmic applications of the immersion order: An overview of ongoing work presented at the Third Slovenian International Conference on Graph Theory, Terminal-pairability in complete bipartite graphs with non-bipartite demands. Edge-disjoint paths in complete bipartite graphs, A Simple 2-Approximation for Maximum-Leaf Spanning Tree, Order Reconfiguration under Width Constraints, Splitter theorems for 4-regular graphs, A new algorithm for finding trees with many leaves, The structure of graphs not admitting a fixed immersion, A simple linear-time algorithm for finding path-decompositions of small width, Complete graph immersions in dense graphs, Well quasi orders in subclasses of bounded treewidth graphs and their algorithmic applications, Tailored heuristics in adaptive large neighborhood search applied to the cutwidth minimization problem, Derivation of algorithms for cutwidth and related graph layout parameters, On problems without polynomial kernels, Well-Quasi-Orders in Subclasses of Bounded Treewidth Graphs, Minimal antichains in well-founded quasi-orders with an application to tournaments, Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth, Myhill-Nerode Methods for Hypergraphs