Genus Characterizes the Complexity of Graph Problems: Some Tight Results
Authors:
- 18 June 2003
- book chapter
- Published by Springer Nature in Lecture Notes in Computer Science
- p. 845-856
Abstract
No abstract availableKeywords
This publication has 9 references indexed in Scilit:
- Vertex Cover: Further Observations and Further ImprovementsJournal of Algorithms, 2001
- Parameterized Complexity1999
- Complexity and Approximation1999
- Proof verification and the hardness of approximation problemsJournal of the ACM, 1998
- Algorithmic graph embeddingsTheoretical Computer Science, 1997
- A note on approximating graph genusInformation Processing Letters, 1997
- Approximation algorithms for NP-complete problems on planar graphsJournal of the ACM, 1994
- The graph genus problem is NP-completeJournal of Algorithms, 1989
- Applications of a Planar Separator TheoremSIAM Journal on Computing, 1980