WEKO3
-
RootNode
アイテム
A Linear Edge Kernel for Two-Layer Crossing Minimization
https://ipsj.ixsq.nii.ac.jp/records/91767
https://ipsj.ixsq.nii.ac.jp/records/91767abce989e-be6d-4599-b6a3-39b9f9a6deef
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL13144004.pdf (454.7 kB)
|
Copyright (c) 2013 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2013-05-10 | |||||||
| タイトル | ||||||||
| タイトル | A Linear Edge Kernel for Two-Layer Crossing Minimization | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | A Linear Edge Kernel for Two-Layer Crossing Minimization | |||||||
| 言語 | ||||||||
| 言語 | eng | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| Meiji University | ||||||||
| 著者所属 | ||||||||
| Meiji University | ||||||||
| 著者所属 | ||||||||
| Business Information Technical Systems | ||||||||
| 著者所属 | ||||||||
| Meiji University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Meiji University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Meiji University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Business Information Technical Systems | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Meiji University | ||||||||
| 著者名 |
Yasuaki, Kobayashi
Hirokazu, Maruta
Yusuke, Nakae
Hisao, Tamaki
× Yasuaki, Kobayashi Hirokazu, Maruta Yusuke, Nakae Hisao, Tamaki
|
|||||||
| 著者名(英) |
Yasuaki, Kobayashi
Hirokazu, Maruta
Yusuke, Nakae
Hisao, Tamaki
× Yasuaki, Kobayashi Hirokazu, Maruta Yusuke, Nakae Hisao, Tamaki
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | We consider a simple generalization of two-layer crossing minimization problem (TLCM) called leaf-edge-weighted TLCM (LEW-TLCM), where we allow positive weights on edges incident to leaves, and show that this problem admits a kernel with O(k) edges provided that the given graph is connected. As a straightforward consequence, LEW-TLCM (and hence TLCM) has a fixed parameter algorithm that runs in 2O(k log k) + nO(1) time which improves on the previously best known algorithm with running time 2O(k3)n. | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | We consider a simple generalization of two-layer crossing minimization problem (TLCM) called leaf-edge-weighted TLCM (LEW-TLCM), where we allow positive weights on edges incident to leaves, and show that this problem admits a kernel with O(k) edges provided that the given graph is connected. As a straightforward consequence, LEW-TLCM (and hence TLCM) has a fixed parameter algorithm that runs in 2O(k log k) + nO(1) time which improves on the previously best known algorithm with running time 2O(k3)n. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN1009593X | |||||||
| 書誌情報 |
研究報告アルゴリズム（AL） 巻 2013-AL-144, 号 4, p. 1-4, 発行日 2013-05-10 |
|||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
