WEKO3
アイテム
Graph orientation with splits
http://hdl.handle.net/10228/00008987
http://hdl.handle.net/10228/0000898740a470c7-2e1c-4e9a-bb21-13a81c989b8c
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
10358853.pdf (227.2 kB)
|
|
| アイテムタイプ | 学術雑誌論文 = Journal Article(1) | |||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2022-10-20 | |||||||||||||
| 資源タイプ | ||||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||||||||
| 資源タイプ | journal article | |||||||||||||
| タイトル | ||||||||||||||
| タイトル | Graph orientation with splits | |||||||||||||
| 言語 | ||||||||||||||
| 言語 | eng | |||||||||||||
| 著者 |
Asahiro, Yuichi
× Asahiro, Yuichi× Jansson, Jesper× 宮野, 英次
WEKO
6037
× Nikpey, Hesam× Ono, Hirotaka |
|||||||||||||
| 抄録 | ||||||||||||||
| 内容記述タイプ | Abstract | |||||||||||||
| 内容記述 | The Minimum Maximum Outdegree Problem (MMO) is to assign a direction to every edge in an input undirected, edge-weighted graph so that the maximum weighted outdegree taken over all vertices becomes as small as possible. In this paper, we introduce a new variant of MMO called the p-Split Minimum Maximum Outdegree Problem (p-Split-MMO) in which one is allowed to perform a sequence of p split operations on the vertices before orienting the edges, for some specified non-negative integer p, and study its computational complexity. | |||||||||||||
| 書誌情報 |
Theoretical Computer Science 巻 844, p. 16-25, 発行日 2020-10-20 |
|||||||||||||
| 出版社 | ||||||||||||||
| 出版者 | Elsevier | |||||||||||||
| DOI | ||||||||||||||
| 関連タイプ | isVersionOf | |||||||||||||
| 識別子タイプ | DOI | |||||||||||||
| 関連識別子 | https://doi.org/10.1016/j.tcs.2020.07.013 | |||||||||||||
| ISSN | ||||||||||||||
| 収録物識別子タイプ | ISSN | |||||||||||||
| 収録物識別子 | 0304-3975 | |||||||||||||
| 著作権関連情報 | ||||||||||||||
| 権利情報 | Copyright (c) 2020 Elsevier B.V. All rights reserved. | |||||||||||||
| キーワード | ||||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | Graph orientation | |||||||||||||
| キーワード | ||||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | Maximum flow | |||||||||||||
| キーワード | ||||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | Vertex cover | |||||||||||||
| キーワード | ||||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | Partition | |||||||||||||
| キーワード | ||||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | Algorithm | |||||||||||||
| キーワード | ||||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | Computational complexity | |||||||||||||
| 出版タイプ | ||||||||||||||
| 出版タイプ | AM | |||||||||||||
| 出版タイプResource | http://purl.org/coar/version/c_ab4af688f83e57aa | |||||||||||||
| 査読の有無 | ||||||||||||||
| 値 | yes | |||||||||||||
| 研究者情報 | ||||||||||||||
| URL | https://hyokadb02.jimu.kyutech.ac.jp/html/233_ja.html | |||||||||||||
| 論文ID（連携） | ||||||||||||||
| 値 | 10358853 | |||||||||||||
| 連携ID | ||||||||||||||
| 値 | 10665 | |||||||||||||
