| アイテムタイプ |
学術雑誌論文 = Journal Article(1) |
| 公開日 |
2023-12-21 |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_6501 |
|
資源タイプ |
journal article |
| タイトル |
|
|
タイトル |
Upper and lower degree-constrained graph orientation with minimum penalty |
|
言語 |
en |
| その他のタイトル |
|
|
その他のタイトル |
Upper and Lower Degree-Constrained Graph Orientation with Minimum Penalty |
|
言語 |
en |
| 言語 |
|
|
言語 |
eng |
| 著者 |
Asahiro, Yuichi
Jansson, Jesper
宮野, 英次
Ono, Hirotaka
|
| 抄録 |
|
|
内容記述タイプ |
Abstract |
|
内容記述 |
In the degree-constrained graph orientation problem, the input is an unweighted, undirected graph G = (V, E) and nonnegative integers av and bv (with av ≤bv) for each v ∈ V, and the objective is to assign a direction to every edge in E in such a way that for each v ∈ V, the number of outgoing edges in the resulting directed graph lies in the interval [av, bv]. When such an orientation does not exist, it is desirable to find an orientation that best fits the condition instead. In this paper, we consider the problem of finding an orientation that minimizes the total penalty Σv ∈ V cv, where cv is a penalty incurred whenever a vertex v violates its degree constraints. As penalty functions, convex, concave, and step functions are considered in this paper. We show that the problem with any convex penalty function can be solved in O(|E|1.5 min{log(|E|・C),|E|0.5 logΔlog|E|}) time, where Δ and C are the maximum degree and the largest magnitude of a penalty, respectively. In contrast, we show APX-hardness of the problem with step or concave functions. For trees and graphs with treewidth τ, the problem with any penalty function can be solved exactly in O(|V|logΔ) time and O(γ2Δ2γ＋2|V|)time, respectively. Finally, we consider the generalization of the problem to edge-weighted graphs and establish strong bounds on its inapproximability that hold even in the special case of stars. On the positive side, we can extend our algorithms for unweighted version of the problem to obtain pseudo-polynomial-time algorithms for the edge-weighted problem variant when restricted to trees and graphs with bounded treewidth. Also, we design a PTAS and a linear-time algorithm for stars with further restrictions on the degree constraints and edge weights. |
|
言語 |
en |
| 書誌情報 |
en : Theoretical Computer Science
巻 900,
p. 53-78,
発行日 2021-12-21
|
| 出版社 |
|
|
出版者 |
Elsevier |
| DOI |
|
|
関連タイプ |
isVersionOf |
|
|
識別子タイプ |
URI |
|
|
関連識別子 |
https://doi.org/10.1016/j.tcs.2021.11.019 |
| NCID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AA00862688 |
| ISSN |
|
|
収録物識別子タイプ |
EISSN |
|
収録物識別子 |
1879-2294 |
| ISSN |
|
|
収録物識別子タイプ |
PISSN |
|
収録物識別子 |
0304-3975 |
| 著作権関連情報 |
|
|
権利情報 |
Copyright (c) 2021 Elsevier B.V. All rights reserved. |
| 出版タイプ |
|
|
出版タイプ |
AM |
|
出版タイプResource |
http://purl.org/coar/version/c_ab4af688f83e57aa |
| 査読の有無 |
|
|
値 |
yes |
| 研究者情報 |
|
|
URL |
https://hyokadb02.jimu.kyutech.ac.jp/html/233_ja.html |
10384229.pdf (468 KB)
