Graph orientation with splits

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

doi:10.1016/j.tcs.2020.07.013

Graph orientation with splits

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

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

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
Pages (from-to)	16-25
Number of pages	10
Journal	Theoretical Computer Science
Volume	844
DOIs	https://doi.org/10.1016/j.tcs.2020.07.013
Publication status	Published - 6 Dec 2020

Keywords

Algorithm
Computational complexity
Graph orientation
Maximum flow
Partition
Vertex cover

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

More information

10.1016/j.tcs.2020.07.013

Cite this

@article{5a6e5d93983e4c5b85cec556ad3368f4,

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

note = "Funding Information: The authors would like to thank an anonymous reviewer of the 5th International Symposium on Combinatorial Optimization (ISCO2018) for providing a simple idea that led to Theorem 12 , and also thank Richard Lemence and Edelia Braga for some discussions related to the topic of this paper. This work was partially supported by JSPS KAKENHI Grant Numbers JP17K00016 and JP17K00024 , JST CREST JPMJR1402 , and PolyU Fund 1-ZE8L . Publisher Copyright: {\textcopyright} 2020 Elsevier B.V. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.",

year = "2020",

month = dec,

day = "6",

doi = "10.1016/j.tcs.2020.07.013",

language = "English",

volume = "844",

pages = "16--25",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

}

TY - JOUR

T1 - Graph orientation with splits

AU - Asahiro, Yuichi

AU - Jansson, Jesper Andreas

AU - Miyano, Eiji

AU - Nikpey, Hesam

AU - Ono, Hirotaka

N1 - Funding Information: The authors would like to thank an anonymous reviewer of the 5th International Symposium on Combinatorial Optimization (ISCO2018) for providing a simple idea that led to Theorem 12 , and also thank Richard Lemence and Edelia Braga for some discussions related to the topic of this paper. This work was partially supported by JSPS KAKENHI Grant Numbers JP17K00016 and JP17K00024 , JST CREST JPMJR1402 , and PolyU Fund 1-ZE8L . Publisher Copyright: © 2020 Elsevier B.V. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.

PY - 2020/12/6

Y1 - 2020/12/6

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=85088399688&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2020.07.013

DO - 10.1016/j.tcs.2020.07.013

M3 - Journal article

AN - SCOPUS:85088399688

SN - 0304-3975

VL - 844

SP - 16

EP - 25

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -

Graph orientation with splits

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this