講演抄録/キーワード |
講演名 |
2018-03-05 14:50
A recognition algorithm for simple-triangle graphs ○Asahi Takaoka(Kanagawa Univ.) COMP2017-50 |
抄録 |
(和) |
A simple-triangle graph is the intersection graph of triangles that are defined by a point on a horizontal line and an interval on another horizontal line. The time complexity of the recognition problem for simple-triangle graphs was a longstanding open problem, which was recently settled. This paper provides a new recognition algorithm for simple-triangle graphs to improve the time bound from $O(n^2 overline{m})$ to $O(nm)$, where $n$, $m$, and $overline{m}$ are the number of vertices, edges, and non-edges of the graph, respectively. The algorithm uses the vertex ordering characterization in our previous paper that a graph is a simple-triangle graph if and only if there is a linear ordering of the vertices containing both an alternating orientation of the graph and a transitive orientation of the complement of the graph. We also show, as a byproduct, that an alternating orientation can be obtained in $O(nm)$ time for cocomparability graphs, and it is NP-complete to decide whether a cocomparability graph has an orientation that is alternating and acyclic. |
(英) |
A simple-triangle graph is the intersection graph of triangles that are defined by a point on a horizontal line and an interval on another horizontal line. The time complexity of the recognition problem for simple-triangle graphs was a longstanding open problem, which was recently settled. This paper provides a new recognition algorithm for simple-triangle graphs to improve the time bound from $O(n^2 overline{m})$ to $O(nm)$, where $n$, $m$, and $overline{m}$ are the number of vertices, edges, and non-edges of the graph, respectively. The algorithm uses the vertex ordering characterization in our previous paper that a graph is a simple-triangle graph if and only if there is a linear ordering of the vertices containing both an alternating orientation of the graph and a transitive orientation of the complement of the graph. We also show, as a byproduct, that an alternating orientation can be obtained in $O(nm)$ time for cocomparability graphs, and it is NP-complete to decide whether a cocomparability graph has an orientation that is alternating and acyclic. |
キーワード |
(和) |
Alternately orientable graphs / Cocomparability graphs / Intersection graphs / PI graphs / Recognition algorithm / Simple-triangle graphs / Vertex ordering characterization / |
(英) |
Alternately orientable graphs / Cocomparability graphs / Intersection graphs / PI graphs / Recognition algorithm / Simple-triangle graphs / Vertex ordering characterization / |
文献情報 |
信学技報, vol. 117, no. 474, COMP2017-50, pp. 27-34, 2018年3月. |
資料番号 |
COMP2017-50 |
発行日 |
2018-02-26 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2017-50 |
|