Graph Orientation with Edge Modifications
| Autor: | T P Sandhya, Eiji Miyano, Jesper Jansson, Hirotaka Ono, Yuichi Asahiro |
|---|---|
| Rok vydání: | 2019 |
| Předmět: | |
| Zdroj: | Frontiers in Algorithmics ISBN: 9783030181253 FAW |
| DOI: | 10.1007/978-3-030-18126-0_4 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|