Graph Orientation with Splits

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

doi:10.1007/978-3-319-96151-4_5

Graph Orientation with Splits

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

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-review

2 Citations (Scopus)

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.

Original language	English
Title of host publication	Combinatorial Optimization - 5th International Symposium, ISCO 2018, Revised Selected Papers
Editors	Jon Lee, A. Ridha Mahjoub, Giovanni Rinaldi
Publisher	Springer-Verlag
Pages	52-63
Number of pages	12
ISBN (Print)	9783319961507
DOIs	https://doi.org/10.1007/978-3-319-96151-4_5
Publication status	Published - 1 Jan 2018
Event	5th International Symposium on Combinatorial Optimization, ISCO 2018 - Marrakesh, Morocco Duration: 11 Apr 2018 → 13 Apr 2018

Publication series

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

Conference

Conference	5th International Symposium on Combinatorial Optimization, ISCO 2018
Country/Territory	Morocco
City	Marrakesh
Period	11/04/18 → 13/04/18

Keywords

Algorithm
Computational complexity
Graph orientation
Maximum flow
Partition
Vertex cover

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

More information

10.1007/978-3-319-96151-4_5

Cite this

Asahiro, Y., Jansson, J. A., Miyano, E., Nikpey, H., & Ono, H. (2018). Graph Orientation with Splits. In J. Lee, A. R. Mahjoub, & G. Rinaldi (Eds.), Combinatorial Optimization - 5th International Symposium, ISCO 2018, Revised Selected Papers (pp. 52-63). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10856 LNCS). Springer-Verlag. https://doi.org/10.1007/978-3-319-96151-4_5

Asahiro, Yuichi ; Jansson, Jesper Andreas ; Miyano, Eiji et al. / Graph Orientation with Splits. Combinatorial Optimization - 5th International Symposium, ISCO 2018, Revised Selected Papers. editor / Jon Lee ; A. Ridha Mahjoub ; Giovanni Rinaldi. Springer-Verlag, 2018. pp. 52-63 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{b5e0c34e7b7f4ba6b92c3e1f1edadf67,

title = "Graph Orientation with Splits",

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.",

keywords = "Algorithm, Computational complexity, Graph orientation, Maximum flow, Partition, Vertex cover",

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

year = "2018",

month = jan,

day = "1",

doi = "10.1007/978-3-319-96151-4_5",

language = "English",

isbn = "9783319961507",

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

publisher = "Springer-Verlag",

pages = "52--63",

editor = "Jon Lee and Mahjoub, {A. Ridha} and Giovanni Rinaldi",

booktitle = "Combinatorial Optimization - 5th International Symposium, ISCO 2018, Revised Selected Papers",

note = "5th International Symposium on Combinatorial Optimization, ISCO 2018 ; Conference date: 11-04-2018 Through 13-04-2018",

}

Asahiro, Y, Jansson, JA, Miyano, E, Nikpey, H & Ono, H 2018, Graph Orientation with Splits. in J Lee, AR Mahjoub & G Rinaldi (eds), Combinatorial Optimization - 5th International Symposium, ISCO 2018, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10856 LNCS, Springer-Verlag, pp. 52-63, 5th International Symposium on Combinatorial Optimization, ISCO 2018, Marrakesh, Morocco, 11/04/18. https://doi.org/10.1007/978-3-319-96151-4_5

Graph Orientation with Splits. / Asahiro, Yuichi; Jansson, Jesper Andreas; Miyano, Eiji et al.
Combinatorial Optimization - 5th International Symposium, ISCO 2018, Revised Selected Papers. ed. / Jon Lee; A. Ridha Mahjoub; Giovanni Rinaldi. Springer-Verlag, 2018. p. 52-63 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10856 LNCS).

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-review

TY - GEN

T1 - Graph Orientation with Splits

AU - Asahiro, Yuichi

AU - Jansson, Jesper Andreas

AU - Miyano, Eiji

AU - Nikpey, Hesam

AU - Ono, Hirotaka

PY - 2018/1/1

Y1 - 2018/1/1

N2 - 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.

AB - 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.

KW - Algorithm

KW - Computational complexity

KW - Graph orientation

KW - Maximum flow

KW - Partition

KW - Vertex cover

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

U2 - 10.1007/978-3-319-96151-4_5

DO - 10.1007/978-3-319-96151-4_5

M3 - Conference article published in proceeding or book

AN - SCOPUS:85050623726

SN - 9783319961507

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

SP - 52

EP - 63

BT - Combinatorial Optimization - 5th International Symposium, ISCO 2018, Revised Selected Papers

A2 - Lee, Jon

A2 - Mahjoub, A. Ridha

A2 - Rinaldi, Giovanni

PB - Springer-Verlag

T2 - 5th International Symposium on Combinatorial Optimization, ISCO 2018

Y2 - 11 April 2018 through 13 April 2018

ER -

Asahiro Y, Jansson JA, Miyano E, Nikpey H, Ono H. Graph Orientation with Splits. In Lee J, Mahjoub AR, Rinaldi G, editors, Combinatorial Optimization - 5th International Symposium, ISCO 2018, Revised Selected Papers. Springer-Verlag. 2018. p. 52-63. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-96151-4_5

Graph Orientation with Splits

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this