Nonconstructive tools for proving polynomial-time decidability
From MaRDI portal
Recommendations
Cited in
(63)- Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction
- Minimum-weight cycle covers and their approximability
- Nonconstructive advances in polynomial-time complexity
- Constructive complexity
- The vertex separation number of a graph equals its path-width
- Diagonalization, uniformity, and fixed-point theorems
- Improved self-reduction algorithms for graphs with bounded treewidth
- Obstruction set isolation for the gate matrix layout problem
- 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
- On interval routing schemes and treewidth
- On computing graph minor obstruction sets
- Algorithms and obstructions for linear-width and related search parameters
- Well quasi orders in subclasses of bounded treewidth graphs and their algorithmic applications
- A linear time algorithm for monadic querying of indefinite data over linearly ordered domains
- Computing crossing numbers in quadratic time
- From the \(W\)-hierarchy to XNLP. Classes of fixed parameter intractability
- Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover
- Parameterized computation and complexity: a new approach dealing with NP-hardness
- A randomized algorithm for long directed cycle
- Hitting forbidden minors: approximation and kernelization
- FPT is characterized by useful obstruction sets: connecting algorithms, kernels, and quasi-orders
- Taming the incomputable, reconstructing the nonconstructive and deciding the undecidable in mathematical economics
- Fixed-parameter tractability, a prehistory
- The birth and early years of parameterized complexity
- A basic parameterized complexity primer
- Fixed-parameter tractability of treewidth and pathwidth
- Surfing with Rod
- Algorithms and complexity of signed, minus, and majority domination
- scientific article; zbMATH DE number 4110103 (Why is no real title available?)
- A minimum degree condition forcing complete graph immersion
- Polynomial-time self-reducibility: theoretical motivations and practical results∗
- A decidability result for the dominating set problem
- Constructivity issues in graph algorithms
- Finite automata as characterizations of minor closed tree families (extended abstract)
- Confronting intractability via parameters
- On feedback vertex set: new measure and new structures
- Kernelization of Arc Disjoint Cycle Packing in \alpha -Bounded Digraphs
- A mathematical commitment without computational strength
- The parallel complexity of tree embedding problems (extended abstract)
- A Linear-Time Parameterized Algorithm for Node Unique Label Cover
- Complete graph immersions in dense graphs
- A naive algorithm for feedback vertex set
- List-coloring graphs without subdivisions and without immersions
- The parameterized complexity of cycle packing: indifference is not an issue
- k-apices of minor-closed graph classes. I: Bounding the obstructions
- Kernelization of arc disjoint cycle packing in -bounded digraphs
- On Interval Routing Schemes and treewidth
- A lower bound for treewidth and its consequences
- A note on the self-witnessing property of computational problems
- The genus of regular languages and directed graph emulators
- Faster parameterized algorithms for minor containment
- The complexity of querying indefinite data about linearly ordered domains
- An FPT-algorithm for recognizing k-apices of minor-closed graph classes
- When recursion is better than iteration: a linear-time algorithm for directed acyclicity with few error vertices
- Delineating half-integrality of the Erdős-Pósa property for minors: the case of surfaces
- Graph parameters, universal obstructions, and WQO
- Connected graph searching
- Linearizing well quasi-orders and bounding the length of bad sequences
- Searching for an evader in an unknown dark cave by an optimal number of asynchronous searchers
- Linear-time algorithms for problems on planar graphs with fixed disk dimension
- Quickly deciding minor-closed parameters in general graphs
- On well-quasi-ordering finite structures with labels
This page was built for publication: Nonconstructive tools for proving polynomial-time decidability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3798236)
