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)

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

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)