Problems remaining NP-complette for sparse or dense graphs

DOI10.7151/dmgt.1004zbMath0829.05042OpenAlexW2054643041MaRDI QIDQ4846683

Ingo Schiermeyer

Publication date: 8 November 1995

Published in: Discussiones Mathematicae Graph Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.7151/dmgt.1004

zbMATH Keywords

computational complexityNP-completenessindependent setHamiltonian circuitNP-completeHamiltonian path

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Eulerian and Hamiltonian graphs (05C45)

Related Items (5)

Hamiltonian Cycle in K1,r-Free Split Graphs — A Dichotomy ⋮ Improved approximation for spanning star forest in dense graphs ⋮ Going Far from Degeneracy ⋮ Unnamed Item ⋮ Maximum independent sets near the upper bound

This page was built for publication: Problems remaining NP-complette for sparse or dense graphs