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