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

}