| 大会名称 |
| 2016年 総合大会 |
| 大会コ－ド |
| 2016G |
| 開催年 |
|
2016
|
| 発行日 |
|
2016/3/1
|
| セッション番号 |
|
AS-1
|
| セッション名 |
|
グラフ理論の工学的魅力を語る － 基礎から最前線の応用まで
|
| 講演日 |
|
2016/3/17
|
| 講演場所(会議室等) |
|
総合学習プラザ 2F 第16講義室
|
| 講演番号 |
|
AS-1-6
|
| タイトル |
|
A Polynomial-Time Algorithm for a Variation of the 2-Chain Subgraph Cover Problem Related to the Recognition of Simple-Triangle Graphs
|
| 著者名 |
|
○Asahi TAKAOKA,
|
| キーワード |
|
Chain cover, PI graphs, Simple-triangle graphs
|
| 抄録 |
|
A simple-triangle graph is an intersection graph of upward triangles between two horizontal lines such that the base of every triangle is on the bottom line and the apex of every triangle is on the top line. The recognition problem of simple-triangle graphs can be solved in polynomial time by reducing it to a variation of the 2-chain subgraph cover problem, which can be reduced to a tractable subclass of 3-satisfiability (3SAT). This paper shows that the problem can be reduced to 2-satisfiability (2SAT).
|
| 本文pdf |
|
PDF download
|
