Nonconstructive tools for proving polynomial-time decidability
From MaRDI portal
Publication:3798236
DOI10.1145/44483.44491zbMath0652.68049OpenAlexW1987092466WikidataQ55881135 ScholiaQ55881135MaRDI QIDQ3798236
Michael A. Langston, Michael R. Fellows
Publication date: 1988
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/44483.44491
Analysis of algorithms and problem complexity (68Q25) Partial orders, general (06A06) Graph theory (including graph drawing) in computer science (68R10)
Related Items
A randomized algorithm for long directed cycle, Searching for an evader in an unknown dark cave by an optimal number of asynchronous searchers, Kernelization of Arc Disjoint Cycle Packing in $$\alpha $$-Bounded Digraphs, Improved self-reduction algorithms for graphs with bounded treewidth, Obstruction set isolation for the gate matrix layout problem, A MATHEMATICAL COMMITMENT WITHOUT COMPUTATIONAL STRENGTH, A linear time algorithm for monadic querying of indefinite data over linearly ordered domains, Computing crossing numbers in quadratic time, On search, decision, and the efficiency of polynomial-time algorithms, Linear-time algorithms for problems on planar graphs with fixed disk dimension, 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, Nonconstructive advances in polynomial-time complexity, Quickly deciding minor-closed parameters in general graphs, From the \(W\)-hierarchy to XNLP. Classes of fixed parameter intractability, Polynomial-time self-reducibility: theoretical motivations and practical results∗, 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, The parallel complexity of tree embedding problems (extended abstract), Effective computation of immersion obstructions for unions of graph classes, A minimum degree condition forcing complete graph immersion, \(k\)-apices of minor-closed graph classes. I: Bounding the obstructions, Kernelization of arc disjoint cycle packing in \(\alpha\)-bounded digraphs, A decidability result for the dominating set problem, On Interval Routing Schemes and treewidth, A lower bound for treewidth and its consequences, A note on the self-witnessing property of computational problems, Surfing with Rod, On well-quasi-ordering finite structures with labels, A naive algorithm for feedback vertex set, Faster parameterized algorithms for minor containment, Confronting intractability via parameters, Finite automata as characterizations of minor closed tree families (extended abstract), Constructive complexity, On feedback vertex set: new measure and new structures, The complexity of querying indefinite data about linearly ordered domains, Complete graph immersions in dense graphs, The vertex separation number of a graph equals its path-width, Diagonalization, uniformity, and fixed-point theorems, Connected graph searching, Well quasi orders in subclasses of bounded treewidth graphs and their algorithmic applications, Hitting Forbidden Minors: Approximation and Kernelization, Linearizing well quasi-orders and bounding the length of bad sequences, The parameterized complexity of cycle packing: indifference is not an issue, Algorithms and Complexity of Signed, Minus, and Majority Domination, Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction, FPT is characterized by useful obstruction sets, Minimum-weight cycle covers and their approximability, On computing graph minor obstruction sets, A Linear-Time Parameterized Algorithm for Node Unique Label Cover, Algorithms and obstructions for linear-width and related search parameters, Fast fixed-parameter tractable algorithms for nontrivial generalizations of vertex cover, Parameterized computation and complexity: a new approach dealing with NP-hardness, Unnamed Item, TAMING THE INCOMPUTABLE, RECONSTRUCTING THE NONCONSTRUCTIVE AND DECIDING THE UNDECIDABLE IN MATHEMATICAL ECONOMICS
