Graph orientation with splits

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

Research output: Journal article publicationJournal articleAcademic researchpeer-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 languageEnglish
Pages (from-to)16-25
Number of pages10
JournalTheoretical Computer Science
Volume844
DOIs
Publication statusPublished - 6 Dec 2020

Keywords

  • Algorithm
  • Computational complexity
  • Graph orientation
  • Maximum flow
  • Partition
  • Vertex cover

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this