The Computer Journal · 2007 · 26 citations · 34 references
ComputingComputer ScienceMathematicsAlgorithmsGeometryTheory Of ComputationComplexity TheoryComputational ComplexityParameterized AlgorithmsGeometric PredicatesParameterized ComplexityParameterized Complexity Classes
This paper surveys parameterized complexity results for hard geometric algorithmic problems. It includes fixed-parameter tractable problems in graph drawing, geometric graphs, geometric covering and several other areas, together with an overview of the algorithmic techniques used. Fixed-parameter intractability results are surveyed as well. Finally, we give some directions for future research.
34
Michael R. Fellows · Electronic Notes in Theoretical Computer Science · 2002 · 2.9K citations · Full text
Linear Programming in Linear Time When the Dimension Is Fixed
Nimrod Megiddo · Journal of the ACM · 1984 · 676 citations · Full text