The NP-completeness column: An ongoing guide
From MaRDI portal
Publication:5896419
DOI10.1016/0196-6774(84)90032-4zbMath0546.68025OpenAlexW4238118247MaRDI QIDQ5896419
Publication date: 1984
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0196-6774(84)90032-4
Analysis of algorithms and problem complexity (68Q25) Problem books (00A07) Graph theory (including graph drawing) in computer science (68R10)
Related Items
Some properties of sets tractable under every polynomial-time computable distribution ⋮ On the IO-complexity and approximation languages ⋮ Bin-packing ⋮ Resolving Braess's paradox in random networks ⋮ Rankable distributions do not provide harder instances than uniform distributions ⋮ Unnamed Item ⋮ Reductions and convergence rates of average time ⋮ Classifying the computational complexity of problems ⋮ Average case completeness ⋮ A Random NP-complete problem for inversion of 2D cellular automata ⋮ On the theory of average case complexity ⋮ Complete problems with L-samplable distributions ⋮ An Average Case NP-complete Graph Colouring Problem ⋮ Notes on Levin’s Theory of Average-Case Complexity ⋮ A simple linear expected time algorithm for finding a Hamilton path ⋮ Complete problems with L-samplable distributions
