| アイテムタイプ |
学術雑誌論文 = Journal Article(1) |
| 公開日 |
2023-07-31 |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_6501 |
|
資源タイプ |
journal article |
| タイトル |
|
|
タイトル |
Graph Orientation with Splits |
|
言語 |
en |
| 言語 |
|
|
言語 |
eng |
| 著者 |
Asahiro, Yuichi
Jansson, Jesper
宮野, 英次
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. |
|
言語 |
en |
| 備考 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
5th International Symposium on Combinatorial Optimization, ISCO 2018, April 11-13, 2018, Marrakesh, Morocco |
|
言語 |
en |
| 書誌情報 |
en : Lecture Notes in Computer Science
巻 10856,
p. 52-63,
発行日 2018-07-18
|
| 出版社 |
|
|
出版者 |
Springer |
| DOI |
|
|
|
識別子タイプ |
DOI |
|
|
関連識別子 |
https://doi.org/10.1007/978-3-319-96151-4_5 |
| ISBN |
|
|
|
識別子タイプ |
ISBN |
|
|
関連識別子 |
978-3-319-96150-7 |
| ISBN |
|
|
|
識別子タイプ |
ISBN |
|
|
関連識別子 |
978-3-319-96151-4 |
| ISSN |
|
|
収録物識別子タイプ |
EISSN |
|
収録物識別子 |
1611-3349 |
| ISSN |
|
|
収録物識別子タイプ |
PISSN |
|
収録物識別子 |
0302-9743 |
| 著作権関連情報 |
|
|
権利情報 |
Copyright (c) 2018 Springer International Publishing AG, part of Springer Nature. This is a post-peer-review, pre-copyedit version of an article published in Lecture Notes in Computer Science. The final authenticated version is available online at: https://doi.org/10.1007/978-3-319-96151-4_5 |
| キーワード |
|
|
主題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 |
978-3-319-96151-4_5.pdf (211 KB)
