The NP-completeness column: An ongoing guide
From MaRDI portal
Publication:5893778
DOI10.1016/0196-6774(87)90043-5zbMath0626.68039OpenAlexW4232553506MaRDI QIDQ5893778
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
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items (19)
Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths ⋮ Graph Minors and Parameterized Algorithm Design ⋮ The VC-dimension of set systems defined by graphs ⋮ Polynomial-time self-reducibility: theoretical motivations and practical results∗ ⋮ NC algorithms for computing the number of perfect matchings in \(K_{3,3}\)-free graphs and related problems ⋮ Sequential Relational Decomposition ⋮ An Improved Algorithm for Finding Cycles Through Elements ⋮ VC-dimensions for graphs (extended abstract) ⋮ Unnamed Item ⋮ The monadic second-order logic of graphs : Definable sets of finite graphs ⋮ Constructive complexity ⋮ Mixed searching and proper-path-width ⋮ Detecting cycles through three fixed vertices in a graph ⋮ The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs ⋮ Self-witnessing polynomial-time complexity and prime factorization ⋮ Diagonalization, uniformity, and fixed-point theorems ⋮ A polynomial algorithm for recognizing bounded cutwidth in hypergraphs ⋮ Structure and recognition of graphs with no 6-wheel subdivision ⋮ Minimal antichains in well-founded quasi-orders with an application to tournaments
This page was built for publication: The NP-completeness column: An ongoing guide
