The NP-completeness column: An ongoing guide
From MaRDI portal
Publication:5903516
DOI10.1016/0196-6774(87)90021-6zbMath0633.68022OpenAlexW4243764894MaRDI QIDQ5903516
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)90021-6
Related Items (25)
Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis ⋮ Entropy, Randomization, Derandomization, and Discrepancy ⋮ Template-Based Minor Embedding for Adiabatic Quantum Optimization ⋮ Local search is a PTAS for feedback vertex set in minor-free graphs ⋮ On permuting some coordinates of polytopes ⋮ The effect of homogeneity on the computational complexity of combinatorial data anonymization ⋮ The maximum edge biclique problem is NP-complete ⋮ On the complexity of the black-and-white coloring problem on some classes of perfect graphs ⋮ Unit disk graphs ⋮ On-line partitioning of width \(w\) posets into \(w^{O(\log\log w)}\) chains ⋮ \(\alpha\)-vertex separator is NP-hard even for 3-regular graphs ⋮ Edge colouring line graphs of unicyclic graphs ⋮ Lower Bounds for Kernelizations and Other Preprocessing Procedures ⋮ Lower bounds for kernelizations and other preprocessing procedures ⋮ Consensus algorithms for the generation of all maximal bicliques ⋮ Combinatorics and algorithms for quasi-chain graphs ⋮ Combinatorics and algorithms for quasi-chain graphs ⋮ On the complexity of finding balanced oneway cuts ⋮ The Effect of Homogeneity on the Complexity of k-Anonymity ⋮ Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction ⋮ Finding optimal volume subintervals with \( k\) points and calculating the star discrepancy are NP-hard problems ⋮ A note on the complexity of the bilevel bottleneck assignment problem ⋮ On the pathwidth of chordal graphs ⋮ Finding maximum cliques in arbitrary and in special graphs ⋮ The structure of the models of decidable monadic theories of graphs
This page was built for publication: The NP-completeness column: An ongoing guide
