Veröffentlichung

Titel:

Solving Optimization Problems on Orthogonal Ray Graphs

AutorInnen:

Steven Chaplick
Fabian Lipp
Philipp Kindermann
Alexander Wolff

Kategorie:

Workshopbeiträge

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.} }