Nonconstructive advances in polynomial-time complexity
From MaRDI portal
Publication:1098635
DOI10.1016/0020-0190(87)90054-8zbMath0637.68053DBLPjournals/ipl/FellowsL87OpenAlexW2000611521WikidataQ57360197 ScholiaQ57360197MaRDI QIDQ1098635
Michael R. Fellows, Michael A. Langston
Publication date: 1987
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(87)90054-8
Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99)
Related Items (22)
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 ⋮ 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 ⋮ The Impact of Parameterized Complexity to Interdisciplinary Problem Solving ⋮ A Basic Parameterized Complexity Primer ⋮ Fixed-Parameter Tractability of Treewidth and Pathwidth ⋮ From the \(W\)-hierarchy to XNLP. Classes of fixed parameter intractability ⋮ Polynomial-time self-reducibility: theoretical motivations and practical results∗ ⋮ A decidability result for the dominating set problem ⋮ Connections between cutting-pattern sequencing, VLSI design, and flexible machines ⋮ Surfing with Rod ⋮ Constructive complexity ⋮ LP Formulations for Polynomial Optimization Problems ⋮ The complexity of querying indefinite data about linearly ordered domains ⋮ A brief history of Edward K. Blum and the Journal of Computer and System Sciences ⋮ The vertex separation number of a graph equals its path-width ⋮ A multiple-population evolutionary approach to gate matrix layout ⋮ A partial k-arboretum of graphs with bounded treewidth ⋮ On problems without polynomial kernels
Cites Work
This page was built for publication: Nonconstructive advances in polynomial-time complexity
