On approximating the longest path in a graph
- 1 May 1997
- journal article
- Published by Springer Nature in Algorithmica
- Vol. 18 (1), 82-98
- https://doi.org/10.1007/bf02523689
Abstract
No abstract availableKeywords
This publication has 15 references indexed in Scilit:
- Approximating clique is almost NP-completePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Some tools for approximate 3-coloringPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- The NP-completeness column: An ongoing guideJournal of Algorithms, 1992
- On the complexity of approximating the independent set problemInformation and Computation, 1992
- Proof verification and hardness of approximation problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1992
- Probabilistic checking of proofs; a new characterization of NPPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1992
- Finding hidden Hamiltonian cyclesPublished by Association for Computing Machinery (ACM) ,1991
- Bin packing can be solved within 1 + ε in linear timeCombinatorica, 1981
- Edmonds polytopes and weakly hamiltonian graphsMathematical Programming, 1973
- Tough graphs and hamiltonian circuitsDiscrete Mathematics, 1973