| アイテムタイプ |
学術雑誌論文 = Journal Article(1) |
| 公開日 |
2023-08-10 |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_6501 |
|
資源タイプ |
journal article |
| タイトル |
|
|
タイトル |
How to Pack Directed Acyclic Graphs into Small Blocks |
|
言語 |
en |
| 言語 |
|
|
言語 |
eng |
| 著者 |
Asahiro, Yuichi
Furukawa, Tetsuya
Ikegami, Keiichi
宮野, 英次
|
| 抄録 |
|
|
内容記述タイプ |
Abstract |
|
内容記述 |
The paper studies the following variant of clustering or laying out problems of graphs: Given a directed acyclic graph (DAG for short), the objective is to find a mapping of its nodes into blocks of size at most B that minimizes the maximum number of external arcs during traversals of the acyclic structure by following paths from the roots to the leaves. An external arc is defined as an arc connecting two distinct blocks. The problem can be shown to be NP-hard generally, and to remain intractable even if B = 2 and the height of DAGs is three. In this paper we provide a 3/2 factor linear time approximation algorithm for B = 2, and prove that the 3/2 ratio is optimal in terms of approximation guarantee. In the case of B ≥ 3, we also show that there is no 3/2−ε factor approximation algorithm assuming P ≠ NP, where ε is arbitrarily small positive. Furthermore, we give a 2 factor approximation algorithm for B = 3 if the input is restricted to a set of layered graphs. |
| 備考 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
6th Italian Conference on Algorithms and Complexity, CIAC 2006, Rome, Italy, 29 - 31 May, 2006 |
| 書誌情報 |
Lecture Notes in Computer Science
巻 3998,
p. 272-283,
発行日 2006
|
| 出版社 |
|
|
出版者 |
Springer |
| DOI |
|
|
|
識別子タイプ |
DOI |
|
|
関連識別子 |
https://doi.org/10.1007/11758471_27 |
| ISBN |
|
|
|
識別子タイプ |
ISBN |
|
|
関連識別子 |
978-3-540-34375-2 |
| ISBN |
|
|
|
識別子タイプ |
ISBN |
|
|
関連識別子 |
978-3-540-34378-3 |
| 著作権関連情報 |
|
|
権利情報 |
Copyright (c) 2006 Springer-Verlag Berlin Heidelberg |
| 出版タイプ |
|
|
出版タイプ |
AM |
|
出版タイプResource |
http://purl.org/coar/version/c_ab4af688f83e57aa |
| 査読の有無 |
|
|
値 |
yes |
| 研究者情報 |
|
|
URL |
https://hyokadb02.jimu.kyutech.ac.jp/html/233_ja.html |
10347759.pdf (162 KB)
