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.} }
Christoph Doppelbauer | 25.06.2019