WEKO3
アイテム
How to pack directed acyclic graphs into small blocks
http://hdl.handle.net/10228/0002000012
http://hdl.handle.net/10228/000200001201ef603f-ac34-4125-8b95-adf22d4de095
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
j.dam.2020.08.005.pdf (999 KB)
|
|
| Item type | 学術雑誌論文 = Journal Article(1) | |||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2023-07-31 | |||||||||||||||||||||
| 資源タイプ | ||||||||||||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||||||||||||||||
| 資源タイプ | journal article | |||||||||||||||||||||
| タイトル | ||||||||||||||||||||||
| タイトル | How to pack directed acyclic graphs into small blocks | |||||||||||||||||||||
| 言語 | en | |||||||||||||||||||||
| その他のタイトル | ||||||||||||||||||||||
| その他のタイトル | How to Pack Directed Acyclic Graphs into Small Blocks | |||||||||||||||||||||
| 言語 | en | |||||||||||||||||||||
| 言語 | ||||||||||||||||||||||
| 言語 | eng | |||||||||||||||||||||
| 著者 |
Asahiro, Yuichi
× Asahiro, Yuichi
× Furukawa, Tetsuya
× Ikegami, Keiichi
× 宮野, 英次
WEKO
6037
× Yagita, Tsuyoshi
|
|||||||||||||||||||||
| 抄録 | ||||||||||||||||||||||
| 内容記述タイプ | Abstract | |||||||||||||||||||||
| 内容記述 | This paper studies the following variant of clustering or laying out problems for directed acyclic graphs (DAG for short), called the minimum block transfer problem. The objective of this problem is to find a partition of a node set which satisfies the following two conditions: (i) Each element (called a block) of the partition has a size that is at most B and (ii) the maximum number of external arcs among directed paths from the roots to the leaves is minimized. Here, an external arc is defined as an arc connecting two distinct blocks. This paper mainly studies the case B = 2. First, we show that the problem is NP-hard even if the height of DAGs is three and its maximum indegree and outdegree are two and three, respectively. Then, we design (i) linear-time optimal algorithms for DAGs of height at most two, (ii) a very simple 2-approximation algorithm, and moreover, (iii) a (2−2/h)-approximation algorithm for the case that the height h of the input DAG is even and the other one for odd h, whose approximation ratio is 2−2/(h+1). As for the inapproximability of the problem, for any xi >0 and unless P = NP, we show that the problem does not admit any polynomial time (3/2 – xi)-approximation ((4/3− xi)-approximation, resp.) algorithm if the height of the input DAGs is restricted to at most five (at least six, resp.). Also, in the case B ≥3, we show the NP-hardness and prove a (3/2− xi)-inapproximability of this case. | |||||||||||||||||||||
| 書誌情報 |
en : Discrete Applied Mathematics 巻 288, p. 91-113, 発行日 2020-08-29 |
|||||||||||||||||||||
| 出版社 | ||||||||||||||||||||||
| 出版者 | Elsevier | |||||||||||||||||||||
| DOI | ||||||||||||||||||||||
| 識別子タイプ | DOI | |||||||||||||||||||||
| 関連識別子 | https://doi.org/10.1016/j.dam.2020.08.005 | |||||||||||||||||||||
| ISSN | ||||||||||||||||||||||
| 収録物識別子タイプ | PISSN | |||||||||||||||||||||
| 収録物識別子 | 0166-218X | |||||||||||||||||||||
| ISSN | ||||||||||||||||||||||
| 収録物識別子タイプ | EISSN | |||||||||||||||||||||
| 収録物識別子 | 1872-6771 | |||||||||||||||||||||
| 著作権関連情報 | ||||||||||||||||||||||
| 権利情報 | Copyright (c) 2020 Elsevier B.V. All rights reserved. | |||||||||||||||||||||
| キーワード | ||||||||||||||||||||||
| 主題Scheme | Other | |||||||||||||||||||||
| 主題 | Minimum block transfer problem | |||||||||||||||||||||
| キーワード | ||||||||||||||||||||||
| 主題Scheme | Other | |||||||||||||||||||||
| 主題 | Directed acyclic graph | |||||||||||||||||||||
| キーワード | ||||||||||||||||||||||
| 主題Scheme | Other | |||||||||||||||||||||
| 主題 | NP-hardness | |||||||||||||||||||||
| キーワード | ||||||||||||||||||||||
| 主題Scheme | Other | |||||||||||||||||||||
| 主題 | Approximability | |||||||||||||||||||||
| キーワード | ||||||||||||||||||||||
| 主題Scheme | Other | |||||||||||||||||||||
| 主題 | Inapproximability | |||||||||||||||||||||
| キーワード | ||||||||||||||||||||||
| 主題Scheme | Other | |||||||||||||||||||||
| 主題 | Greedy algorithm | |||||||||||||||||||||
| 出版タイプ | ||||||||||||||||||||||
| 出版タイプ | AM | |||||||||||||||||||||
| 出版タイプResource | http://purl.org/coar/version/c_ab4af688f83e57aa | |||||||||||||||||||||
| 査読の有無 | ||||||||||||||||||||||
| 値 | yes | |||||||||||||||||||||
| 研究者情報 | ||||||||||||||||||||||
| URL | https://hyokadb02.jimu.kyutech.ac.jp/html/233_ja.html | |||||||||||||||||||||
