Degree-Constrained Graph Orientation: Maximum Satisfaction and Minimum Violation

Yuichi Asahiro; Jesper Andreas Jansson; Eiji Miyano; Hirotaka Ono

doi:10.1007/s00224-014-9565-5

Degree-Constrained Graph Orientation: Maximum Satisfaction and Minimum Violation

Yuichi Asahiro, Jesper Andreas Jansson, Eiji Miyano, Hirotaka Ono

Research output: Journal article publication › Journal article › Academic research › peer-review

10 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 reference (Asahiro et al. LNCS 7422, 332–343 (2012)): For any fixed non-negative integer W, the problems MAXW-LIGHT, MINW-LIGHT, MAXW-HEAVY, and MINW-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. As shown in Asahiro et al. LNCS 7422, 332–343 (2012)).

Original language	English
Pages (from-to)	60-93
Number of pages	34
Journal	Theory of Computing Systems
Volume	58
Issue number	1
DOIs	https://doi.org/10.1007/s00224-014-9565-5
Publication status	Published - 1 Jan 2016
Externally published	Yes

Keywords

(In)approximability
Degree constraint
Graph orientation
Greedy algorithm
Submodular function

ASJC Scopus subject areas

Theoretical Computer Science
Computational Theory and Mathematics

More information

10.1007/s00224-014-9565-5

Cite this

@article{90d2e6e9062c4522bcda5efc32a7e102,

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 reference (Asahiro et al. LNCS 7422, 332–343 (2012)): For any fixed non-negative integer W, the problems MAXW-LIGHT, MINW-LIGHT, MAXW-HEAVY, and MINW-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. As shown in Asahiro et al. LNCS 7422, 332–343 (2012)).",

keywords = "(In)approximability, Degree constraint, Graph orientation, Greedy algorithm, Submodular function",

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

year = "2016",

month = jan,

day = "1",

doi = "10.1007/s00224-014-9565-5",

language = "English",

volume = "58",

pages = "60--93",

journal = "Theory of Computing Systems",

issn = "1432-4350",

publisher = "Springer New York",

number = "1",

}

TY - JOUR

T1 - Degree-Constrained Graph Orientation: Maximum Satisfaction and Minimum Violation

AU - Asahiro, Yuichi

AU - Jansson, Jesper Andreas

AU - Miyano, Eiji

AU - Ono, Hirotaka

PY - 2016/1/1

Y1 - 2016/1/1

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 reference (Asahiro et al. LNCS 7422, 332–343 (2012)): For any fixed non-negative integer W, the problems MAXW-LIGHT, MINW-LIGHT, MAXW-HEAVY, and MINW-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. As shown in Asahiro et al. LNCS 7422, 332–343 (2012)).

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 reference (Asahiro et al. LNCS 7422, 332–343 (2012)): For any fixed non-negative integer W, the problems MAXW-LIGHT, MINW-LIGHT, MAXW-HEAVY, and MINW-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. As shown in Asahiro et al. LNCS 7422, 332–343 (2012)).

KW - (In)approximability

KW - Degree constraint

KW - Graph orientation

KW - Greedy algorithm

KW - Submodular function

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

U2 - 10.1007/s00224-014-9565-5

DO - 10.1007/s00224-014-9565-5

M3 - Journal article

SN - 1432-4350

VL - 58

SP - 60

EP - 93

JO - Theory of Computing Systems

JF - Theory of Computing Systems

IS - 1

ER -

Degree-Constrained Graph Orientation: Maximum Satisfaction and Minimum Violation

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this