講演抄録/キーワード |
講演名 |
2017-03-07 11:00
Recognizing Simple-Triangle Graphs by Restricted 2-Chain Subgraph Cover ○Asahi Takaoka(Kanagawa Univ.) COMP2016-51 |
抄録 |
(和) |
(まだ登録されていません) |
(英) |
A simple-triangle graph (also known as a PI graph) is the intersection graph of a family of triangles defined by a point on a horizontal line and an interval on another horizontal line. The recognition problem for simple-triangle graphs was a longstanding open problem, and recently a polynomial-time algorithm has been given [G. B. Mertzios, The Recognition of Simple-Triangle Graphs and of Linear-Interval Orders is Polynomial, SIAM J. Discrete Math., 29(3):1150--1185, 2015]. Along with the approach of this paper, we show a simpler recognition algorithm for simple-triangle graphs. To do this, we provide a polynomial-time algorithm to solve the following problem: Given a bipartite graph $G$ and a set $F$ of edges of $G$, find a 2-chain subgraph cover of $G$ such that one of two chain subgraphs has no edges in $F$. This paper is an extended abstract, and some proofs are omitted. |
キーワード |
(和) |
/ / / / / / / |
(英) |
Chain cover / Graph sandwich problem / PI graphs / Simple-triangle graphs / Threshold dimension 2 graphs / / / |
文献情報 |
信学技報, vol. 116, no. 503, COMP2016-51, pp. 5-9, 2017年3月. |
資料番号 |
COMP2016-51 |
発行日 |
2017-02-28 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2016-51 |
研究会情報 |
研究会 |
COMP |
開催期間 |
2017-03-07 - 2017-03-07 |
開催地(和) |
南山大学 |
開催地(英) |
Nanzan University |
テーマ(和) |
|
テーマ(英) |
|
講演論文情報の詳細 |
申込み研究会 |
COMP |
会議コード |
2017-03-COMP |
本文の言語 |
英語 |
タイトル(和) |
|
サブタイトル(和) |
|
タイトル(英) |
Recognizing Simple-Triangle Graphs by Restricted 2-Chain Subgraph Cover |
サブタイトル(英) |
|
キーワード(1)(和/英) |
/ Chain cover |
キーワード(2)(和/英) |
/ Graph sandwich problem |
キーワード(3)(和/英) |
/ PI graphs |
キーワード(4)(和/英) |
/ Simple-triangle graphs |
キーワード(5)(和/英) |
/ Threshold dimension 2 graphs |
キーワード(6)(和/英) |
/ |
キーワード(7)(和/英) |
/ |
キーワード(8)(和/英) |
/ |
第1著者 氏名(和/英/ヨミ) |
高岡 旭 / Asahi Takaoka / タカオカ アサヒ |
第1著者 所属(和/英) |
神奈川大学 (略称: 神奈川大)
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著者 所属(和/英) |
(略称: )
(略称: ) |
第19著者 氏名(和/英/ヨミ) |
/ / |
第19著者 所属(和/英) |
(略称: )
(略称: ) |
第20著者 氏名(和/英/ヨミ) |
/ / |
第20著者 所属(和/英) |
(略称: )
(略称: ) |
講演者 |
第1著者 |
発表日時 |
2017-03-07 11:00:00 |
発表時間 |
30分 |
申込先研究会 |
COMP |
資料番号 |
COMP2016-51 |
巻番号(vol) |
vol.116 |
号番号(no) |
no.503 |
ページ範囲 |
pp.5-9 |
ページ数 |
5 |
発行日 |
2017-02-28 (COMP) |
|