| 大会名称 |
| 2016年 総合大会 |
| 大会コ－ド |
| 2016G |
| 開催年 |
|
2016
|
| 発行日 |
|
2016/3/1
|
| セッション番号 |
|
AS-1
|
| セッション名 |
|
グラフ理論の工学的魅力を語る － 基礎から最前線の応用まで
|
| 講演日 |
|
2016/3/17
|
| 講演場所(会議室等) |
|
総合学習プラザ 2F 第16講義室
|
| 講演番号 |
|
AS-1-3
|
| タイトル |
|
A 3/2-Approximation Algorithm for the Bipartite Dense Subgraph Problem on Bipartite Permutation Graphs
|
| 著者名 |
|
○Yuta Inaba, Satoshi Tayu, Shuichi Ueno,
|
| キーワード |
|
bipartite dense subgraph, bipartite permutation graph, approximation algorithm
|
| 抄録 |
|
The densest k-subgraph problem is to find a k-vertex subgraph of a given graph that has as many edges as possible. The problem is known to be NP-hard even for chordal bipartite graphs. The bipartite dense subgraph problem is a variant of the densest k-subgraph problem, and defined as follows:Given a bipartite graph G with bipartition (X,Y), natural numbers k1 ＜= |X| and k2 ＜= |Y|, find a subgraph H of G such that |V(H) ∩ X| = x, |V(H) ∩ Y | = y, and |E(H)| is maximal. The problem is also NP-hard for bipartite chordal graphs. This paper shows that a 3/2-approximation algorithm to the bipartite dense subgraph problem on n-bipartite permutation graphs can be found in O(k1k2n6) time.
|
| 本文pdf |
|
PDF download
|
