WEKO3
アイテム
節点がレベル付けされたグラフの最小枝交差描画問題に関する一考察
https://ipsj.ixsq.nii.ac.jp/records/32396
https://ipsj.ixsq.nii.ac.jp/records/32396c2e53014-a312-4eac-a94b-baecaf8fbc65
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL94041007.pdf (1.2 MB)
|
Copyright (c) 1994 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 1994-09-21 | |||||||
| タイトル | ||||||||
| タイトル | 節点がレベル付けされたグラフの最小枝交差描画問題に関する一考察 | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | Theories and an Optimal Algorithm for Crossing Number Minimization Prblem in Multi - level Graphs | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| 早稲田大学理工学部 | ||||||||
| 著者所属 | ||||||||
| 拓殖大学工学部 | ||||||||
| 著者所属 | ||||||||
| 早稲田大学理工学部 | ||||||||
| 著者所属 | ||||||||
| 早稲田大学理工学部 | ||||||||
| 著者所属 | ||||||||
| 早稲田大学理工学部 | ||||||||
| 著者所属 | ||||||||
| 拓殖大学工学部 | ||||||||
| 著者所属 | ||||||||
| 早稲田大学理工学部 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| School of Science and Engineering Waseda University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Faculty of Engineering Takushoku University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| School of Science and Engineering Waseda University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| School of Science and Engineering Waseda University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| School of Science and Engineering Waseda University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Faculty of Engineering Takushoku University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| School of Science and Engineering Waseda University | ||||||||
| 著者名 |
松本, 英幸
× 松本, 英幸
|
|||||||
| 著者名(英) |
Hideyuki, Matsumoto
× Hideyuki, Matsumoto
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | グラフの節点がレベル付けされたグラフをマルチレベルグラフという．ここでは，マルチレベルグラフを平面上に描画する際に枝の交差数が最小になるように各レベルの節点順序を決定する問題を取り扱う．このとき，枝は直線分のみで描画されるものとする．この問題は非常に難しい問題のクラスに属することが知られており，これまで近似解法に関する研究に重点が置かれていた．本稿ではまず，この問題に関する従来の研究，諸定理を示す．そして，0?1整数線形計画問題として定式化し，二分決定グラフ(）を用いて最適解を求める解法を提案する．最後に，提案手法を計算機に実装し実験を行った結果を報告する． | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | A graph is called a multi-level graph when each node of the graph is given a hierarchical level. The problem of minimizing the number of edge crossings in a multi-level graphs is discussed, where each edge is drawn with a line-segment. The problem is known to include NP-complete problems. In the first part of this paper, previous works are summarized and several theories are introduced. Then, the problem is formulated by 0-1 integer linear programming, and solved optimally using a binary diagram. Experimental results are also shown. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN1009593X | |||||||
| 書誌情報 |
情報処理学会研究報告アルゴリズム（AL） 巻 1994, 号 82(1994-AL-041), p. 49-56, 発行日 1994-09-21 |
|||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
