Graph Orientation with Splits

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

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-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 languageEnglish
Title of host publicationCombinatorial Optimization - 5th International Symposium, ISCO 2018, Revised Selected Papers
EditorsJon Lee, A. Ridha Mahjoub, Giovanni Rinaldi
PublisherSpringer-Verlag
Pages52-63
Number of pages12
ISBN (Print)9783319961507
DOIs
Publication statusPublished - 1 Jan 2018
Event5th International Symposium on Combinatorial Optimization, ISCO 2018 - Marrakesh, Morocco
Duration: 11 Apr 201813 Apr 2018

Publication series

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

Conference

Conference5th International Symposium on Combinatorial Optimization, ISCO 2018
CountryMorocco
CityMarrakesh
Period11/04/1813/04/18

Keywords

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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this