Graph orientation with edge modifications

Yuichi Asahiro; Jesper Andreas Jansson; Eiji Miyano; Hirotaka Ono; Sandhya Thekkumpadan Puthiyaveedu

doi:10.1007/978-3-030-18126-0_4

Graph orientation with edge modifications

Yuichi Asahiro, Jesper Andreas Jansson, Eiji Miyano, Hirotaka Ono, Sandhya Thekkumpadan Puthiyaveedu

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-review

1 Citation (Scopus)

Abstract

The goal of an outdegree-constrained edge-modification problem is to find a spanning subgraph or supergraph H of an input undirected graph G such that either: (Type I) the number of edges in H is minimized or maximized and H can be oriented to satisfy some specified constraints on the vertices’ resulting outdegrees; or: (Type II) the maximum or minimum outdegree of all vertices under an optimal orientation of H is minimum or maximum among all subgraphs or supergraphs of G that can be constructed by deleting or inserting a fixed number of edges. This paper introduces eight new outdegree-constrained edge-modification problems related to load balancing called (Type I) MIN-DEL-MAX, MIN-INS-MIN, MAX-INS-MAX, and MAX-DEL-MIN and (Type II) p-DEL-MAX, p-INS-MIN, p-INS-MAX, and p-DEL-MIN. We first present a framework that provides algorithms for solving all eight problems in polynomial time on unweighted graphs. Next we investigate the inapproximability of the edge-weighted versions of the problems, and design polynomial-time algorithms for six of the problems on edge-weighted trees.

Original language	English
Title of host publication	Frontiers in Algorithmics - 13th International Workshop, FAW 2019, Proceedings
Editors	Yijia Chen, Xiaotie Deng, Mei Lu
Publisher	Springer-Verlag
Pages	38-50
Number of pages	13
ISBN (Print)	9783030181253
DOIs	https://doi.org/10.1007/978-3-030-18126-0_4
Publication status	Published - 1 Jan 2019
Event	13th International Workshop on Frontiers in Algorithmics, FAW 2019 - Sanya, China Duration: 29 Apr 2019 → 3 May 2019

Publication series

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

Conference

Conference	13th International Workshop on Frontiers in Algorithmics, FAW 2019
Country/Territory	China
City	Sanya
Period	29/04/19 → 3/05/19

Keywords

Computational complexity
Graph orientation
Greedy algorithm
Inapproximability
Load balancing
Maximum flow

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

More information

10.1007/978-3-030-18126-0_4

Cite this

Asahiro, Y., Jansson, J. A., Miyano, E., Ono, H., & Thekkumpadan Puthiyaveedu, S. (2019). Graph orientation with edge modifications. In Y. Chen, X. Deng, & M. Lu (Eds.), Frontiers in Algorithmics - 13th International Workshop, FAW 2019, Proceedings (pp. 38-50). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11458 LNCS). Springer-Verlag. https://doi.org/10.1007/978-3-030-18126-0_4

Asahiro, Yuichi ; Jansson, Jesper Andreas ; Miyano, Eiji et al. / Graph orientation with edge modifications. Frontiers in Algorithmics - 13th International Workshop, FAW 2019, Proceedings. editor / Yijia Chen ; Xiaotie Deng ; Mei Lu. Springer-Verlag, 2019. pp. 38-50 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{436c75cf9b9b4a849aaa0cfe7ef66136,

title = "Graph orientation with edge modifications",

abstract = "The goal of an outdegree-constrained edge-modification problem is to find a spanning subgraph or supergraph H of an input undirected graph G such that either: (Type I) the number of edges in H is minimized or maximized and H can be oriented to satisfy some specified constraints on the vertices{\textquoteright} resulting outdegrees; or: (Type II) the maximum or minimum outdegree of all vertices under an optimal orientation of H is minimum or maximum among all subgraphs or supergraphs of G that can be constructed by deleting or inserting a fixed number of edges. This paper introduces eight new outdegree-constrained edge-modification problems related to load balancing called (Type I) MIN-DEL-MAX, MIN-INS-MIN, MAX-INS-MAX, and MAX-DEL-MIN and (Type II) p-DEL-MAX, p-INS-MIN, p-INS-MAX, and p-DEL-MIN. We first present a framework that provides algorithms for solving all eight problems in polynomial time on unweighted graphs. Next we investigate the inapproximability of the edge-weighted versions of the problems, and design polynomial-time algorithms for six of the problems on edge-weighted trees.",

keywords = "Computational complexity, Graph orientation, Greedy algorithm, Inapproximability, Load balancing, Maximum flow",

author = "Yuichi Asahiro and Jansson, {Jesper Andreas} and Eiji Miyano and Hirotaka Ono and {Thekkumpadan Puthiyaveedu}, Sandhya",

year = "2019",

month = jan,

day = "1",

doi = "10.1007/978-3-030-18126-0_4",

language = "English",

isbn = "9783030181253",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer-Verlag",

pages = "38--50",

editor = "Yijia Chen and Xiaotie Deng and Mei Lu",

booktitle = "Frontiers in Algorithmics - 13th International Workshop, FAW 2019, Proceedings",

note = "13th International Workshop on Frontiers in Algorithmics, FAW 2019 ; Conference date: 29-04-2019 Through 03-05-2019",

}

Asahiro, Y, Jansson, JA, Miyano, E, Ono, H & Thekkumpadan Puthiyaveedu, S 2019, Graph orientation with edge modifications. in Y Chen, X Deng & M Lu (eds), Frontiers in Algorithmics - 13th International Workshop, FAW 2019, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11458 LNCS, Springer-Verlag, pp. 38-50, 13th International Workshop on Frontiers in Algorithmics, FAW 2019, Sanya, China, 29/04/19. https://doi.org/10.1007/978-3-030-18126-0_4

Graph orientation with edge modifications. / Asahiro, Yuichi; Jansson, Jesper Andreas; Miyano, Eiji et al.
Frontiers in Algorithmics - 13th International Workshop, FAW 2019, Proceedings. ed. / Yijia Chen; Xiaotie Deng; Mei Lu. Springer-Verlag, 2019. p. 38-50 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11458 LNCS).

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-review

TY - GEN

T1 - Graph orientation with edge modifications

AU - Asahiro, Yuichi

AU - Jansson, Jesper Andreas

AU - Miyano, Eiji

AU - Ono, Hirotaka

AU - Thekkumpadan Puthiyaveedu, Sandhya

PY - 2019/1/1

Y1 - 2019/1/1

N2 - The goal of an outdegree-constrained edge-modification problem is to find a spanning subgraph or supergraph H of an input undirected graph G such that either: (Type I) the number of edges in H is minimized or maximized and H can be oriented to satisfy some specified constraints on the vertices’ resulting outdegrees; or: (Type II) the maximum or minimum outdegree of all vertices under an optimal orientation of H is minimum or maximum among all subgraphs or supergraphs of G that can be constructed by deleting or inserting a fixed number of edges. This paper introduces eight new outdegree-constrained edge-modification problems related to load balancing called (Type I) MIN-DEL-MAX, MIN-INS-MIN, MAX-INS-MAX, and MAX-DEL-MIN and (Type II) p-DEL-MAX, p-INS-MIN, p-INS-MAX, and p-DEL-MIN. We first present a framework that provides algorithms for solving all eight problems in polynomial time on unweighted graphs. Next we investigate the inapproximability of the edge-weighted versions of the problems, and design polynomial-time algorithms for six of the problems on edge-weighted trees.

AB - The goal of an outdegree-constrained edge-modification problem is to find a spanning subgraph or supergraph H of an input undirected graph G such that either: (Type I) the number of edges in H is minimized or maximized and H can be oriented to satisfy some specified constraints on the vertices’ resulting outdegrees; or: (Type II) the maximum or minimum outdegree of all vertices under an optimal orientation of H is minimum or maximum among all subgraphs or supergraphs of G that can be constructed by deleting or inserting a fixed number of edges. This paper introduces eight new outdegree-constrained edge-modification problems related to load balancing called (Type I) MIN-DEL-MAX, MIN-INS-MIN, MAX-INS-MAX, and MAX-DEL-MIN and (Type II) p-DEL-MAX, p-INS-MIN, p-INS-MAX, and p-DEL-MIN. We first present a framework that provides algorithms for solving all eight problems in polynomial time on unweighted graphs. Next we investigate the inapproximability of the edge-weighted versions of the problems, and design polynomial-time algorithms for six of the problems on edge-weighted trees.

KW - Computational complexity

KW - Graph orientation

KW - Greedy algorithm

KW - Inapproximability

KW - Load balancing

KW - Maximum flow

UR - http://www.scopus.com/inward/record.url?scp=85065303648&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-18126-0_4

DO - 10.1007/978-3-030-18126-0_4

M3 - Conference article published in proceeding or book

AN - SCOPUS:85065303648

SN - 9783030181253

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 38

EP - 50

BT - Frontiers in Algorithmics - 13th International Workshop, FAW 2019, Proceedings

A2 - Chen, Yijia

A2 - Deng, Xiaotie

A2 - Lu, Mei

PB - Springer-Verlag

T2 - 13th International Workshop on Frontiers in Algorithmics, FAW 2019

Y2 - 29 April 2019 through 3 May 2019

ER -

Asahiro Y, Jansson JA, Miyano E, Ono H, Thekkumpadan Puthiyaveedu S. Graph orientation with edge modifications. In Chen Y, Deng X, Lu M, editors, Frontiers in Algorithmics - 13th International Workshop, FAW 2019, Proceedings. Springer-Verlag. 2019. p. 38-50. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-18126-0_4

Graph orientation with edge modifications

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this