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

DOI10.1016/S0022-0000(05)80079-0zbMATH Open0938.68599DBLPjournals/jcss/FellowsL94OpenAlexW2043344835WikidataQ57360134 ScholiaQ57360134MaRDI QIDQ1342869FDOQ1342869

Cites Work

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

Cited In (27)

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

This page was built for publication: On search, decision, and the efficiency of polynomial-time algorithms

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