Abstract
We deal with the problem of finding such an orientation of a given graph that the largest number of edges leaving a vertex (called the outdegree of the orientation) is small.
For any ε∈(0,1) we show an \(\tilde{O}(|E(G)|/\varepsilon)\) time algorithm which finds an orientation of an input graph G with outdegree at most ⌈(1+ε)d *⌉, where d * is the maximum density of a subgraph of G. It is known that the optimal value of orientation outdegree is ⌈d * ⌉.
Our algorithm has applications in constructing labeling schemes, introduced by Kannan et al. in [18] and in approximating such graph density measures as arboricity, pseudoarboricity and maximum density. Our results improve over the previous, 2-approximation algorithms by Aichholzer et al. [1] (for orientation / pseudoarboricity), by Arikati et al. [3] (for arboricity) and by Charikar [5] (for maximum density).
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Aichholzer, O., Aurenhammer, F., Rote, G.: Optimal graph orientation with storage applications. SFB-Report F003-51, SFB Optimierung und Kontrolle, TU Graz, Austria (1995)
Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM 42(4), 844–856 (1995)
Arikati, S.R., Maheshwari, A., Zaroliagis, C.D.: Efficient computation of implicit representations of sparse graphs. Discrete Appl. Math. 78(1-3), 1–16 (1997)
Brodal, G.S., Fagerberg, R.: Dynamic representations of sparse graphs. In: Dehne, F., Gupta, A., Sack, J.-R., Tamassia, R. (eds.) WADS 1999. LNCS, vol. 1663, pp. 342–351. Springer, Heidelberg (1999)
Charikar, M.: Greedy approximation algorithms for finding dense components in a graph. In: Jansen, K., Khuller, S. (eds.) APPROX 2000. LNCS, vol. 1913, pp. 84–95. Springer, Heidelberg (2000)
Chiba, N., Nishizeki, T.: Arboricity and subgraph listing algorithms. SIAM J. Comput. 14(1), 210–223 (1985)
Chrobak, M., Eppstein, D.: Planar orientations with low out-degree and compaction of adjacency matrices. Theoretical Computer Science 86(2), 243–266 (1991)
Eppstein, D.: Arboricity and bipartite subgraph listing algorithms. Inf. Process. Lett. 51(4), 207–211 (1994)
Eppstein, D.: All maximal independent sets and dynamic dominance for sparse graphs. In: Proc. 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), pp. 451–459 (2005)
Even, S., Tarjan, R.E.: Network flow and testing graph connectivity. SIAM J. Comput. 4(4), 507–518 (1975)
Frank, A., Gyárfás, A.: How to orient the edges of a graph? In: Hajnal, A., Sós, V.T. (eds.) Proc. of the Fifth Hungarian Colloquium on Combinatorics, Keszthely, vol. I, pp. 353–364. North-Holland, Amsterdam (1976)
Gabow, H.: Upper degree-constrained partial orientations. In: Proc. 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2006) (2006)
Gabow, H., Westermann, H.: Forests, frames, and games: algorithms for matroid sums and applications. In: Proc. of the 20th Annual ACM Symposium on Theory of Computing (STOC 1988), pp. 407–421. ACM Press, New York (1988)
Galil, Z., Naamad, A.: An O(EVlog2 V) algorithm for the maximal flow problem. J. Comput. System Sci. 21, 203–217 (1980)
Gallo, G., Grigoriadis, M.D., Tarjan, R.E.: A fast parametric maximum flow algorithm and applications. SIAM J. Comput. 18(1), 30–55 (1989)
Goldberg, A.V.: Finding a maximum density subgraph. Technical Report UCB/CSD-84-171, EECS Department, University of California, Berkeley (1984)
Goldberg, A.V., Rao, S.: Beyond the flow decomposition barrier. In: Proc. of the 38th Annual Symposium on Foundations of Computer Science (FOCS 1997), p. 2. IEEE Computer Society Press, Washington, DC, USA (1997)
Kannan, S., Naor, M., Rudich, S.: Implicit representation of graphs. In: Proc. of the 20th Annual ACM Symposium on Theory of Computing (STOC 1988), pp. 334–343. ACM Press, New York (1988)
Kowalik, Ł., Kurowski, M.: Shortest path queries in planar graphs in constant time. In: Proc. 35th Symposium on Theory of Computing (STOC 2003), pp. 143–148. ACM, New York (2003)
Kozen, D.C.: The design and analysis of algorithms. Springer, New York (1992)
Nash-Williams, C.S.J.A.: Decomposition of finite graphs into forests. Journal of the London Mathematical Society 39, 12 (1964)
Picard, J.-C., Queyranne, M.: A network flow solution to some nonlinear 0-1 programming problems with application to graph theory. Networks 12, 141–159 (1982)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kowalik, Ł. (2006). Approximation Scheme for Lowest Outdegree Orientation and Graph Density Measures. In: Asano, T. (eds) Algorithms and Computation. ISAAC 2006. Lecture Notes in Computer Science, vol 4288. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11940128_56
Download citation
DOI: https://doi.org/10.1007/11940128_56
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-49694-6
Online ISBN: 978-3-540-49696-0
eBook Packages: Computer ScienceComputer Science (R0)