お知らせ 研究会の開催と会場に参加される皆様へのお願い（2020年10月開催～）
 電子情報通信学会 研究会発表申込システム 講演論文 詳細 技報閲覧サービス [ログイン] 技報アーカイブ
 トップに戻る 前のページに戻る [Japanese] / [English]

 講演抄録／キーワード 講演名 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

 研究会情報 研究会 COMP 開催期間 2018-03-05 - 2018-03-05 開催地（和） 大阪府立大学 開催地（英） Osaka Prefecture Univ. テーマ（和） テーマ（英） 講演論文情報の詳細 申込み研究会 COMP 会議コード 2018-03-COMP 本文の言語 英語 タイトル（和） サブタイトル（和） タイトル（英） A recognition algorithm for simple-triangle graphs サブタイトル（英） キーワード(1)（和/英） Alternately orientable graphs / Alternately orientable graphs キーワード(2)（和/英） Cocomparability graphs / Cocomparability graphs キーワード(3)（和/英） Intersection graphs / Intersection graphs キーワード(4)（和/英） PI graphs / PI graphs キーワード(5)（和/英） Recognition algorithm / Recognition algorithm キーワード(6)（和/英） Simple-triangle graphs / Simple-triangle graphs キーワード(7)（和/英） Vertex ordering characterization / Vertex ordering characterization キーワード(8)（和/英） / 第1著者 氏名（和/英/ヨミ） Asahi Takaoka / Asahi Takaoka / 第1著者 所属（和/英） Kanagawa University (略称： Kanagawa Univ.) Kanagawa University (略称： Kanagawa Univ.) 第2著者 氏名（和/英/ヨミ） / / 第2著者 所属（和/英） (略称： ) (略称： ) 第3著者 氏名（和/英/ヨミ） / / 第3著者 所属（和/英） (略称： ) (略称： ) 第4著者 氏名（和/英/ヨミ） / / 第4著者 所属（和/英） (略称： ) (略称： ) 第5著者 氏名（和/英/ヨミ） / / 第5著者 所属（和/英） (略称： ) (略称： ) 第6著者 氏名（和/英/ヨミ） / / 第6著者 所属（和/英） (略称： ) (略称： ) 第7著者 氏名（和/英/ヨミ） / / 第7著者 所属（和/英） (略称： ) (略称： ) 第8著者 氏名（和/英/ヨミ） / / 第8著者 所属（和/英） (略称： ) (略称： ) 第9著者 氏名（和/英/ヨミ） / / 第9著者 所属（和/英） (略称： ) (略称： ) 第10著者 氏名（和/英/ヨミ） / / 第10著者 所属（和/英） (略称： ) (略称： ) 第11著者 氏名（和/英/ヨミ） / / 第11著者 所属（和/英） (略称： ) (略称： ) 第12著者 氏名（和/英/ヨミ） / / 第12著者 所属（和/英） (略称： ) (略称： ) 第13著者 氏名（和/英/ヨミ） / / 第13著者 所属（和/英） (略称： ) (略称： ) 第14著者 氏名（和/英/ヨミ） / / 第14著者 所属（和/英） (略称： ) (略称： ) 第15著者 氏名（和/英/ヨミ） / / 第15著者 所属（和/英） (略称： ) (略称： ) 第16著者 氏名（和/英/ヨミ） / / 第16著者 所属（和/英） (略称： ) (略称： ) 第17著者 氏名（和/英/ヨミ） / / 第17著者 所属（和/英） (略称： ) (略称： ) 第18著者 氏名（和/英/ヨミ） / / 第18著者 所属（和/英） (略称： ) (略称： ) 講演者 1 発表日時 2018-03-05 14:50:00 発表時間 25 申込先研究会 COMP 資料番号 IEICE-COMP2017-50 巻番号（vol） IEICE-117 号番号（no） no.474 ページ範囲 pp.27-34 ページ数 IEICE-8 発行日 IEICE-COMP-2018-02-26

[研究会発表申込システムのトップページに戻る]

[電子情報通信学会ホームページ]

IEICE / 電子情報通信学会