Degree-Constrained Graph Orientation: Maximum Satisfaction and Minimum Violation

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

Research output: Journal article publicationJournal articleAcademic researchpeer-review

9 Citations (Scopus)

Abstract

A degree-constrained graph orientation of an undirected graph G is an assignment of a direction to each edge in G such that the outdegree of every vertex in the resulting directed graph satisfies a specified lower and/or upper bound. Such graph orientations have been studied for a long time and various characterizations of their existence are known. In this paper, we consider four related optimization problems introduced in reference (Asahiro et al. LNCS 7422, 332–343 (2012)): For any fixed non-negative integer W, the problems MAXW-LIGHT, MINW-LIGHT, MAXW-HEAVY, and MINW-HEAVY take as input an undirected graph G and ask for an orientation of G that maximizes or minimizes the number of vertices with outdegree at most W or at least W. As shown in Asahiro et al. LNCS 7422, 332–343 (2012)).
Original languageEnglish
Pages (from-to)60-93
Number of pages34
JournalTheory of Computing Systems
Volume58
Issue number1
DOIs
Publication statusPublished - 1 Jan 2016
Externally publishedYes

Keywords

  • (In)approximability
  • Degree constraint
  • Graph orientation
  • Greedy algorithm
  • Submodular function

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computational Theory and Mathematics

Cite this