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

DOI10.1137/0405010MaRDI QIDQ3989017zbMATH OpenOpenAlexFDO

Authors Michael R. Fellows, Michael A. Langston

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

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

Cited in

(29)

• Order Reconfiguration under Width Constraints
• On problems without polynomial kernels
• Parameterized complexity of graph burning
• Splitter theorems for 4-regular graphs
• A Simple 2-Approximation for Maximum-Leaf Spanning Tree
• Improved self-reduction algorithms for graphs with bounded treewidth
• Complete graph immersions in dense graphs
• Kernelization for finding lineal topologies (depth-first spanning trees) with many or few leaves
• A mathematical commitment without computational strength
• Tailored heuristics in adaptive large neighborhood search applied to the cutwidth minimization problem
• scientific article; zbMATH DE number 4110103 (Why is no real title available?)
• A simple linear-time algorithm for finding path-decompositions of small width
• Terminal-pairability in complete bipartite graphs with non-bipartite demands. Edge-disjoint paths in complete bipartite graphs
• Experimental evaluation of a branch-and-bound algorithm for computing pathwidth and directed pathwidth
• scientific article; zbMATH DE number 4133491 (Why is no real title available?)
• On search, decision, and the efficiency of polynomial-time algorithms
• On algorithmic applications of the immersion order: An overview of ongoing work presented at the Third Slovenian International Conference on Graph Theory
• Well quasi orders in subclasses of bounded treewidth graphs and their algorithmic applications
• Derivation of algorithms for cutwidth and related graph layout parameters
• Fixed-parameter tractability of treewidth and pathwidth
• scientific article; zbMATH DE number 4064479 (Why is no real title available?)
• Approximating the pathwidth of outerplanar graphs
• Well-quasi-orders in subclasses of bounded treewidth graphs
• Minimal antichains in well-founded quasi-orders with an application to tournaments
• Obstruction set isolation for the gate matrix layout problem
• The structure of graphs not admitting a fixed immersion
• A new algorithm for finding trees with many leaves
• Constructivity issues in graph algorithms
• Fixed-parameter tractability, a prehistory

This page was built for publication: On Well-Partial-Order Theory and Its Application to Combinatorial Problems of VLSI Design

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