On search, decision, and the efficiency of polynomial-time algorithms

DOI10.1016/S0022-0000(05)80079-0zbMath0938.68599OpenAlexW2043344835WikidataQ57360134 ScholiaQ57360134MaRDI QIDQ1342869

Michael R. Fellows, Michael A. Langston

Publication date: 21 June 2000

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0022-0000(05)80079-0

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Nonnumerical algorithms (68W05)

Related Items

Bounding the search number of graph products, Fixed-Parameter Tractability of Treewidth and Pathwidth, Graph Minors and Parameterized Algorithm Design, Combining intensification and diversification strategies in VNS. An application to the vertex separation problem, Variable neighborhood search for the vertex separation problem, A tight lower bound for vertex planarization on graphs of bounded treewidth, On algorithmic applications of the immersion order: An overview of ongoing work presented at the Third Slovenian International Conference on Graph Theory, On interval routing schemes and treewidth, On minimum cost edge searching, Effective computation of immersion obstructions for unions of graph classes, \(k\)-apices of minor-closed graph classes. I: Bounding the obstructions, Terminal-pairability in complete bipartite graphs with non-bipartite demands. Edge-disjoint paths in complete bipartite graphs, Low Polynomial Exclusion of Planar Graph Patterns, On Interval Routing Schemes and treewidth, Obtaining a planar graph by vertex deletion, A note on the self-witnessing property of computational problems, Unnamed Item, Confronting intractability via parameters, Unnamed Item, Explicit linear kernels for packing problems, A brief history of Edward K. Blum and the Journal of Computer and System Sciences, Complete graph immersions in dense graphs, Fast minor testing in planar graphs, Algorithms and obstructions for linear-width and related search parameters, Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover, Myhill-Nerode Methods for Hypergraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Theorie der Normalflächen. Ein Isotopiekriterium für den Kreisknoten
• Graph minors. V. Excluding a planar graph
• Nonconstructive advances in polynomial-time complexity
• Riemann's hypothesis and tests for primality
• Graph minors. XIII: The disjoint paths problem
• Graph minors. IV: Tree-width and well-quasi-ordering
• Nonconstructive tools for proving polynomial-time decidability
• On Well-Partial-Order Theory and Its Application to Combinatorial Problems of VLSI Design