Parameterized Complexity of Geometric Problems

by: Panos Giannopoulos, Christian Knauer, Sue Whitesides

The Computer Journal, Vol. 51, No. 3. (1 May 2008), pp. 372-384.

View FullText article

DOI, HighWire

Reviews [Write a review of this article]

There are no reviews of this article

Find related articles from these CiteULike users

AbnerCYH

Find related articles with these CiteULike tags

algorithms, geometries, parameterized

Abstract

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. 10.1093/comjnl/bxm053

@article{citeulike:2746037, abstract = {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. 10.1093/comjnl/bxm053}, author = {Giannopoulos, Panos and Knauer, Christian and Whitesides, Sue }, citeulike-article-id = {2746037}, doi = {10.1093/comjnl/bxm053}, journal = {The Computer Journal}, keywords = {algorithms, geometries, parameterized}, month = {May}, number = {3}, pages = {372--384}, posted-at = {2008-05-02 15:57:51}, priority = {2}, title = {Parameterized Complexity of Geometric Problems}, url = {http://dx.doi.org/10.1093/comjnl/bxm053}, volume = {51}, year = {2008} }

RIS record

TY - JOUR ID - citeulike:2746037 L3 - citeulike-article-id:2746037 TI - Parameterized Complexity of Geometric Problems JF - The Computer Journal VL - 51 IS - 3 SP - 372 EP - 384 N2 - 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. 10.1093/comjnl/bxm053 KW - algorithms KW - geometries KW - parameterized AU - Giannopoulos, Panos AU - Knauer, Christian AU - Whitesides, Sue PY - 2008/05/01/ UR - http://dx.doi.org/10.1093/comjnl/bxm053 ER -

RIS BibTeX