The NP-completeness column: An ongoing guide

DOI10.1016/0196-6774(87)90043-5zbMath0626.68039MaRDI QIDQ5893778

David S. Johnson

Publication date: 1987

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0196-6774(87)90043-5

zbMATH Keywords

polynomial time; hidden constants; non-constructive proofs

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

Related Items

A polynomial algorithm for recognizing bounded cutwidth in hypergraphs, Mixed searching and proper-path-width, Structure and recognition of graphs with no 6-wheel subdivision, NC algorithms for computing the number of perfect matchings in \(K_{3,3}\)-free graphs and related problems, Constructive complexity, Detecting cycles through three fixed vertices in a graph, Self-witnessing polynomial-time complexity and prime factorization, Diagonalization, uniformity, and fixed-point theorems, The VC-dimension of set systems defined by graphs, Minimal antichains in well-founded quasi-orders with an application to tournaments, Graph Minors and Parameterized Algorithm Design, An Improved Algorithm for Finding Cycles Through Elements, Polynomial-time self-reducibility: theoretical motivations and practical results^∗