Logo der Fakultät Logo LG Theoretische Informatik
 

Veröffentlichung

Titel:

Solving Optimization Problems on Orthogonal Ray Graphs

AutorInnen: Steven Chaplick
Fabian Lipp
Philipp Kindermann
Alexander Wolff
Kategorie: Anleitungen
erschienen in: Proceedings of the 18th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCGG^2 2015)
Abstract:

In this paper we study the class of orthogonal ray graphs (ORGs). An ORG is the intersection graph of axis-parallel rays. We distinguish two subclasses of ORG, which limit the directions for the rays to two (2DORG) or three (3DORG) directions. There are several characterizations for 2DORGs and a polynomial-time recognition algorithm. We achieve some results towards a similar characterization for 3DORGs.

Afterwards, we look at some well-known combinatorial problems (e.g., MIS and FVS), which are NP-hard on general graphs. We can solve these problems in polynomial times on ORGs and also give specialized algorithms for 2DORGs and 3DORGs.

Download: Abstract
BibTeX-Eintrag: @InProceedings{CLKW15, Title = {Solving Optimization Problems on Orthogonal Ray Graphs}, Author = {Steven Chaplick and Fabian Lipp and Philipp Kindermann and Alexander Wolff}, Booktitle = {Proceedings of the 18th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCGG^2 15)}, Year = {2015}, Note = {Abstract}, Abstract = {In this paper we study the class of orthogonal ray graphs (ORGs). An ORG is the intersection graph of axis-parallel rays. We distinguish two subclasses of ORG, which limit the directions for the rays to two (2DORG) or three (3DORG) directions. There are several characterizations for 2DORGs and a polynomial-time recognition algorithm. We achieve some results towards a similar characterization for 3DORGs. Afterwards, we look at some well-known combinatorial problems (e.g., MIS and FVS), which are NP-hard on general graphs. We can solve these problems in polynomial times on ORGs and also give specialized algorithms for 2DORGs and 3DORGs.} }
Christoph Doppelbauer | 22.11.2016
FernUni-Logo FernUniversität in Hagen, LG Theoretische Informatik, 58084 Hagen