Degree-constrained graph orientation: Maximum satisfaction and minimum violation

Yuichi Asahiro; Jesper Jansson; Eiji Miyano; Hirotaka Ono

doi:10.1007/978-3-319-08001-7_3

Degree-constrained graph orientation: Maximum satisfaction and minimum violation

Yuichi Asahiro, Jesper Jansson, Eiji Miyano, Hirotaka Ono

mathematics and information

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

3 Citations (Scopus)

Abstract

A degree-constrained graph orientation of an undirected graph G is an assignment of a direction to each edge in G such that the outdegree of every vertex in the resulting directed graph satisfies a specified lower and/or upper bound. Such graph orientations have been studied for a long time and various characterizations of their existence are known. In this paper, we consider four related optimization problems introduced in [4]: For any fixed non-negative integer W, the problems Max W -Light, Min W -Light, Max W -Heavy, and Min W -Heavy take as input an undirected graph G and ask for an orientation of G that maximizes or minimizes the number of vertices with outdegree at most W or at least W. The problems' computational complexities vary with W. Here, we resolve several open questions related to their polynomial-time approximability and present a number of positive and negative results.

Original language	English
Title of host publication	Approximation and Online Algorithms - 11th International Workshop, WAOA 2013, Revised Selected Papers
Publisher	Springer Verlag
Pages	24-36
Number of pages	13
ISBN (Print)	9783319080000
DOIs	https://doi.org/10.1007/978-3-319-08001-7_3
Publication status	Published - 2014
Event	11th International Workshop on Approximation and Online Algorithms, WAOA 2013 - Sophia Antipolis, France Duration: Sept 5 2013 → Sept 6 2013

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8447 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	11th International Workshop on Approximation and Online Algorithms, WAOA 2013
Country/Territory	France
City	Sophia Antipolis
Period	9/5/13 → 9/6/13

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-319-08001-7_3

Cite this

Asahiro, Y., Jansson, J., Miyano, E., & Ono, H. (2014). Degree-constrained graph orientation: Maximum satisfaction and minimum violation. In Approximation and Online Algorithms - 11th International Workshop, WAOA 2013, Revised Selected Papers (pp. 24-36). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8447 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-08001-7_3

Degree-constrained graph orientation: Maximum satisfaction and minimum violation. / Asahiro, Yuichi; Jansson, Jesper; Miyano, Eiji et al.
Approximation and Online Algorithms - 11th International Workshop, WAOA 2013, Revised Selected Papers. Springer Verlag, 2014. p. 24-36 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8447 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Asahiro, Y, Jansson, J, Miyano, E & Ono, H 2014, Degree-constrained graph orientation: Maximum satisfaction and minimum violation. in Approximation and Online Algorithms - 11th International Workshop, WAOA 2013, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8447 LNCS, Springer Verlag, pp. 24-36, 11th International Workshop on Approximation and Online Algorithms, WAOA 2013, Sophia Antipolis, France, 9/5/13. https://doi.org/10.1007/978-3-319-08001-7_3

Asahiro Y, Jansson J, Miyano E, Ono H. Degree-constrained graph orientation: Maximum satisfaction and minimum violation. In Approximation and Online Algorithms - 11th International Workshop, WAOA 2013, Revised Selected Papers. Springer Verlag. 2014. p. 24-36. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-08001-7_3

Asahiro, Yuichi ; Jansson, Jesper ; Miyano, Eiji et al. / Degree-constrained graph orientation : Maximum satisfaction and minimum violation. Approximation and Online Algorithms - 11th International Workshop, WAOA 2013, Revised Selected Papers. Springer Verlag, 2014. pp. 24-36 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{9f88a94c6796481b99c2ddf6070b6eab,

title = "Degree-constrained graph orientation: Maximum satisfaction and minimum violation",

abstract = "A degree-constrained graph orientation of an undirected graph G is an assignment of a direction to each edge in G such that the outdegree of every vertex in the resulting directed graph satisfies a specified lower and/or upper bound. Such graph orientations have been studied for a long time and various characterizations of their existence are known. In this paper, we consider four related optimization problems introduced in [4]: For any fixed non-negative integer W, the problems Max W -Light, Min W -Light, Max W -Heavy, and Min W -Heavy take as input an undirected graph G and ask for an orientation of G that maximizes or minimizes the number of vertices with outdegree at most W or at least W. The problems' computational complexities vary with W. Here, we resolve several open questions related to their polynomial-time approximability and present a number of positive and negative results.",

author = "Yuichi Asahiro and Jesper Jansson and Eiji Miyano and Hirotaka Ono",

note = "Funding Information: Supported by KAKENHI Grant Numbers 21680001, 23500020, 25104521, and 25330018 and The Hakubi Project at Kyoto University.; 11th International Workshop on Approximation and Online Algorithms, WAOA 2013 ; Conference date: 05-09-2013 Through 06-09-2013",

year = "2014",

doi = "10.1007/978-3-319-08001-7_3",

language = "English",

isbn = "9783319080000",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "24--36",

booktitle = "Approximation and Online Algorithms - 11th International Workshop, WAOA 2013, Revised Selected Papers",

address = "Germany",

}

TY - GEN

T1 - Degree-constrained graph orientation

T2 - 11th International Workshop on Approximation and Online Algorithms, WAOA 2013

AU - Asahiro, Yuichi

AU - Jansson, Jesper

AU - Miyano, Eiji

AU - Ono, Hirotaka

N1 - Funding Information: Supported by KAKENHI Grant Numbers 21680001, 23500020, 25104521, and 25330018 and The Hakubi Project at Kyoto University.

PY - 2014

Y1 - 2014

N2 - A degree-constrained graph orientation of an undirected graph G is an assignment of a direction to each edge in G such that the outdegree of every vertex in the resulting directed graph satisfies a specified lower and/or upper bound. Such graph orientations have been studied for a long time and various characterizations of their existence are known. In this paper, we consider four related optimization problems introduced in [4]: For any fixed non-negative integer W, the problems Max W -Light, Min W -Light, Max W -Heavy, and Min W -Heavy take as input an undirected graph G and ask for an orientation of G that maximizes or minimizes the number of vertices with outdegree at most W or at least W. The problems' computational complexities vary with W. Here, we resolve several open questions related to their polynomial-time approximability and present a number of positive and negative results.

AB - A degree-constrained graph orientation of an undirected graph G is an assignment of a direction to each edge in G such that the outdegree of every vertex in the resulting directed graph satisfies a specified lower and/or upper bound. Such graph orientations have been studied for a long time and various characterizations of their existence are known. In this paper, we consider four related optimization problems introduced in [4]: For any fixed non-negative integer W, the problems Max W -Light, Min W -Light, Max W -Heavy, and Min W -Heavy take as input an undirected graph G and ask for an orientation of G that maximizes or minimizes the number of vertices with outdegree at most W or at least W. The problems' computational complexities vary with W. Here, we resolve several open questions related to their polynomial-time approximability and present a number of positive and negative results.

UR - http://www.scopus.com/inward/record.url?scp=84903631659&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84903631659&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-08001-7_3

DO - 10.1007/978-3-319-08001-7_3

M3 - Conference contribution

AN - SCOPUS:84903631659

SN - 9783319080000

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 24

EP - 36

BT - Approximation and Online Algorithms - 11th International Workshop, WAOA 2013, Revised Selected Papers

PB - Springer Verlag

Y2 - 5 September 2013 through 6 September 2013

ER -

Degree-constrained graph orientation: Maximum satisfaction and minimum violation

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this