Abstract
Given an undirected and edge-weighted graph G together with a set of ordered vertex-pairs, called st-pairs, we consider the problems of finding an orientation of all edges in G: min-sum orientation is to minimize the sum of the shortest directed distances between all st-pairs; and min-max orientation is to minimize the maximum shortest directed distance among all st-pairs. In this paper, we first show that both problems are strongly NP-hard for planar graphs even if all edge-weights are identical, and that both problems can be solved in polynomial time for cycles. We then consider the problems restricted to cacti, which form a graph class that contains trees and cycles but is a subclass of planar graphs. Then, min-sum orientation is solvable in polynomial time, whereas min-max orientation remains NP-hard even for two st-pairs. However, based on LP-relaxation, we present a polynomial-time 2-approximation algorithm for min-max orientation. Finally, we give a fully polynomial-time approximation scheme (FPTAS) for min-max orientation on cacti if the number of st-pairs is a fixed constant.
This work is partially supported by Grant-in-Aid for Scientific Research: 20650002, 20700003 and 21680001.
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
Brandstädt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. Society for Industrial and Applied Mathematics, Philadelphia (1999)
Chvátal, V., Thomassen, C.: Distances in orientations of graphs. J. Combinatorial Theory, Series B 24, 61–75 (1978)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)
Hakimi, S.L., Schmeichel, E.F., Young, N.E.: Orienting graphs to optimize reachability. Information Processing Letters 63, 229–235 (1997)
Lee, C.-Y., Lei, L., Pinedo, M.: Current trends in deterministic scheduling. Annals of Operations Research 70, 1–41 (1997)
Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, Reading (1994)
Robbins, H.E.: A theorem on graphs with an application to a problem of traffic control. American Mathematical Monthly 46, 281–283 (1939)
Uehara, R., Uno, Y.: On computing longest paths in small graph classes. International Journal of Foundations of Computer Science 18, 911–930 (2007)
Vazirani, V.V.: Approximation Algorithms. Springer, Heidelberg (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ito, T., Miyamoto, Y., Ono, H., Tamaki, H., Uehara, R. (2009). Route-Enabling Graph Orientation Problems. In: Dong, Y., Du, DZ., Ibarra, O. (eds) Algorithms and Computation. ISAAC 2009. Lecture Notes in Computer Science, vol 5878. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-10631-6_42
Download citation
DOI: https://doi.org/10.1007/978-3-642-10631-6_42
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-10630-9
Online ISBN: 978-3-642-10631-6
eBook Packages: Computer ScienceComputer Science (R0)