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
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
