Nonconstructive advances in polynomial-time complexity
From MaRDI portal
Publication:1098635
DOI10.1016/0020-0190(87)90054-8zbMath0637.68053OpenAlexW2000611521WikidataQ57360197 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
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
