nach oben

Theory of Computing Systems

Erschienen in:

01.01.2016

Degree-Constrained Graph Orientation: Maximum Satisfaction and Minimum Violation

verfasst von: Yuichi Asahiro, Jesper Jansson, Eiji Miyano, Hirotaka Ono

Erschienen in: Theory of Computing Systems | Ausgabe 1/2016

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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 MAX W-LIGHT, MIN W-LIGHT, MAX W-HEAVY, and MIN W-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)).

Vorheriger Artikel Approximately Counting Approximately-Shortest Paths in Directed Acyclic Graphs

Nächster Artikel Min-Sum 2-Paths Problems

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Nur mit Berechtigung zugänglich

The average degree of a vertex in the subgraph G[S] is given by the density |E(S)|/|S|, which implies that there is a vertex of degree at least this value. Since |E(S)|/|S| is not always an integer, the maximum degree of the graph G[S] is at least ⌈|E(S)|/|S|⌉. This is why we use the ceiling function in the definition of the maximum density.

Recall that the minimum cost flow problem (see, e.g., [22]) takes as input a flow network with a specified capacity u _i and cost c _i for each arc a _i, and asks for a flow from the source to the sink of some specified size that has the minimum cost, where the cost is defined as \({\sum }_{a_{i}} c_{i} x_{i}\) and where x _i is the amount of the flow along the arc a _i.

It is not necessary for all U _i’s to satisfy the same condition; i.e., it is possible that U _i is W-light while U _j is (W+1)-heavy for some i≠j.

Algorithm Reverse works as follows: Start with any orientation Λ of G. Select a vertex v ₀ with the highest outdegree in Λ(G), find a directed path \(P = (v_{0}, v_{1}, \dots , v_{k})\) satisfying \(d^{+}_{\Lambda }(v_{i}) \leq d^{+}_{\Lambda }(v_{0})\) for 1≤i≤k−1 and \(d^{+}_{\Lambda }(v_{k}) \leq d^{+}_{\Lambda }(v_{0}) - 2\), flip the direction of every edge along P, and repeat the above process (select a v ₀, etc.) until no such path P exists. Output Λ.

Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows. Prentice Hall (1993)

Asahiro, Y., Jansson, J., Miyano, E., Ono, H.: Graph orientation to maximize the minimum weighted outdegree. Int. J. Found. Comput. Sci. 22(3), 583–601 (2011)MATHMathSciNetCrossRef

Asahiro, Y., Jansson, J., Miyano, E., Ono, H., Zenmyo, K.: Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree. J. Comb. Optim. 22(1), 78–96 (2011)MATHMathSciNetCrossRef

Asahiro, Y., Jansson, J., Miyano, E., Ono, H.: Upper and lower degree bounded graph orientation with minimum penalty. In: Proceedings of CATS 2012. CRPIT Series 128, 139–146 (2012)

Asahiro, Y., Jansson, J., Miyano, E., Ono, H.: Graph orientations optimizing the number of light or heavy vertices. In: Proceedings of ISCO 2012. LNCS 7422, 332–343 (2012)MathSciNet

Asahiro, Y., Miyano, E., Ono, H., Zenmyo, K.: Graph orientation algorithms to minimize the maximum outdegree. Int. J. Found. Comput. Sci. 18(2), 197–215 (2007)MATHMathSciNetCrossRef

Chlebik, M., Chlebikova, J.: Complexity of approximating bounded variants of optimization problems. Theor. Comput. Sci. 354(3), 320–338 (2006)MATHMathSciNetCrossRef

Chrobak, M., Eppstein, D.: Planar orientations with low out-degree and compaction of adjacency matrices. Theor. Comput. Sci. 86(2), 243–266 (1991)MATHMathSciNetCrossRef

Chung, F.R.K., Garey, M.R., Tarjan, R.E.: Strongly connected orientations of mixed multigraphs. Networks 15(4), 477–484 (1985)MATHMathSciNetCrossRef

10.

Dinur, I., Safra, S.: On the hardness of approximating minimum vertex cover. Ann. Math. 162(1), 439–485 (2005)MATHMathSciNetCrossRef

11.

Ebenlendr, T., Krčál, M., Sgall, J.: Graph balancing: A special case of scheduling unrelated parallel machines. Algorithmica 68(1), 62–80 (2014)MATHMathSciNetCrossRef

12.

Feige, U.: Approximating maximum clique by removing subgraphs. SIAM J. Discret. Math. 18(2), 219–225 (2004)MATHMathSciNetCrossRef

13.

Frank, A.: Connections in Combinatorial Optimization. Oxford University Press (2011)

14.

Frank, A., Gyárfás, A.: How to orient the edges of a graph? Combinatorics Volume I, North-Holland, 353–364 (1978)

15.

Gabow, H.N.: Upper degree-constrained partial orientations. In: Proceedings of SODA 2006, 554–563 (2006)

16.

Garey, M., Johnson, D.: Computers and Intractability – A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York (1979)MATH

17.

Goldberg, A.V., Rao, S.: Beyond the flow decomposition barrier. J. ACM 45(5), 783–797 (1998)MATHMathSciNetCrossRef

18.

Hakimi, S.L.: On the degrees of the vertices of a directed graph. J. Frankl. Inst. 279(4), 290–308 (1965)MATHMathSciNetCrossRef

19.

Kowalik, L.: Approximation scheme for lowest outdegree orientation and graph density measures. In: Proceedings of ISAAC 2006. LNCS 4288, 557–566 (2006)MathSciNet

20.

Landau, H.G.: On dominance relations and the structure of animal societies: III The condition for a score structure. Bull. Math. Biophys. 15(2), 143–148 (1953)MathSciNetCrossRef

21.

Nash-Williams, C. St. J.A.: On orientations, connectivity and odd-vertex-pairings in finite graphs. Can. J. Math. 12 (4), 555–567 (1960)MATHMathSciNetCrossRef

22.

Orlin, J.B.: A polynomial time primal network simplex algorithm for minimum cost flows. Math. Program. 97, 109–129 (1997)MathSciNet

23.

Orlin, J.B.: Max flows in O(n m) time, or better. In: Proceedings of STOC 2013, 765–774 (2013)

24.

Robbins, H.E.: A theorem on graphs, with an application to a problem of traffic control. The American Mathematical Monthly 46(5), 281–283 (1939)CrossRef

25.

Schrijver, A.: Combinatorial Optimization. Springer (2003)

26.

Stanley, R.P.: Acyclic orientations of graphs. Discret. Math. 5 (2), 171–178 (1973)MATHCrossRef

27.

Trevisan, L.: Non-approximability results for optimization problems on bounded degree instances. In: Proceedings of STOC 2001, 453–461(2001)

28.

Venkateswaran, V.: Minimizing maximum indegree. Discret. Appl. Math. 143(1-3), 374–378 (2004)MATHMathSciNetCrossRef

29.

Wolsey, L.A.: An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica 2(4), 385–393 (1982)MATHMathSciNetCrossRef

30.

Zuckerman, D.: Linear degree extractors and the inapproximability of Max Clique and Chromatic Number. Theory of Computing 3(1), 103–128 (2007)MathSciNetCrossRef

Titel: Degree-Constrained Graph Orientation: Maximum Satisfaction and Minimum Violation
verfasst von: Yuichi Asahiro
Jesper Jansson
Eiji Miyano
Hirotaka Ono
Publikationsdatum: 01.01.2016
Verlag: Springer US
Erschienen in: Theory of Computing Systems / Ausgabe 1/2016
Print ISSN: 1432-4350
Elektronische ISSN: 1433-0490
DOI: https://doi.org/10.1007/s00224-014-9565-5

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 1/2016

Approximately Counting Approximately-Shortest Paths in Directed Acyclic Graphs

Approximating the Sparsest k-Subgraph in Chordal Graphs

Foreword of the Special Issue Dedicated to the 2013 Workshop on Approximation and Online Algorithms

On Two Continuum Armed Bandit Problems in High Dimensions

Improved Approximation Algorithm for k-level Uncapacitated Facility Location Problem (with Penalties)

Low Dimensional Embeddings of Doubling Metrics

Premium Partner