Augmenting graphs to minimize the diameter. (English) Zbl 1319.68156
Summary: We study the problem of augmenting a weighted graph by inserting edges of bounded total cost while minimizing the diameter of the augmented graph. Our main result is an FPT 4-approximation algorithm for the problem.
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 68W25 | Approximation algorithms |
References:
| [1] | Alon, N., Gyárfás, A., Ruszinkó, M.: Decreasing the diameter of bounded degree graphs. J. Graph Theory 35, 161-172 (1999) · Zbl 0966.05024 · doi:10.1002/1097-0118(200011)35:3<161::AID-JGT1>3.0.CO;2-Y |
| [2] | Bilò, D., Gualà, L., Proietti, G.: Improved approximability and non-approximability results for graph diameter decreasing problems. Theor. Comput. Sci. 417, 12-22 (2012) · Zbl 1234.68127 · doi:10.1016/j.tcs.2011.05.014 |
| [3] | Chepoi, V., Vaxès, Y.: Augmenting trees to meet biconnectivity and diameter constraints. Algorithmica 33(2), 243-262 (2002) · Zbl 1052.68099 · doi:10.1007/s00453-001-0113-8 |
| [4] | Demaine, E.D., Zadimoghaddam, M.: Minimizing the diameter of a network using shortcut edges. In: Proceedings of the 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), pp. 420-431 (2010) · Zbl 1285.68119 |
| [5] | Dodis, Y., Khanna, S.: Designing networks with bounded pairwise distance. In: Proceedings of the 31st Annual ACM Symposium on Theory of Computing (STOC), pp. 750-759 (1999) · Zbl 1345.90032 |
| [6] | Downey, R.G., Fellows, M.R.: Parameterized Complexity. Monographs in Computer Science, Springer (1999) · doi:10.1007/978-1-4612-0515-9 |
| [7] | Erdős, P., Rényi, A., Sós, V.T.: On a problem of graph theory. Studia Sci. Math. Hungar 1, 215-235 (1966) · Zbl 0144.23302 |
| [8] | Flum, J., Grohe, M.: Parameterized Complexity Theory, Texts in Theoretical Computer Science. An EATCS Series, vol. XIV. Springer, Berlin (2006) · Zbl 1143.68016 |
| [9] | Frati, F., Gaspers, S., Gudmundsson, J., Mathieson, L.: Augmenting graphs to minimize the diameter. In: Cai, L., Cheng, S.W., Lam, T.W. (eds.) International Symposium on Algorithms and Computation (ISAAC ’13). LNCS, vol. 8283, pp. 383-393. Springer (2013) · Zbl 1406.68078 |
| [10] | Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34(3), 596-615 (1987) · Zbl 1412.68048 · doi:10.1145/28869.28874 |
| [11] | Fredman, M.L., Willard, D.E.: Trans-dichotomous algorithms for minimum spanning trees and shortest paths. J. Comput. Syst. Sci. 48(3), 533-551 (1994) · Zbl 0806.68057 · doi:10.1016/S0022-0000(05)80064-9 |
| [12] | Gao, Y., Hare, D.R., Nastos, J.: The parametric complexity of graph diameter augmentation. Discret. Appl. Math. 161(10-11), 1626-1631 (2013) · Zbl 1287.05035 · doi:10.1016/j.dam.2013.01.016 |
| [13] | Grigorescu, E.: Decreasing the diameter of cycles. J. Graph Theory 43(4), 299-303 (2003) · Zbl 1026.05064 · doi:10.1002/jgt.10122 |
| [14] | Kapoor, S., Sarwat, M.: Bounded-diameter minimum-cost graph problems. Theory Comput. Syst. 41(4), 779-794 (2007) · Zbl 1148.68040 · doi:10.1007/s00224-006-1305-z |
| [15] | Li, C.L., McCormick, S.T., Simchi-Levi, D.: On the minimum-cardinality-bounded-diameter and the bounded-cardinality-minimum-diameter edge addition problems. Oper. Res. Lett. 11(5), 303-308 (1992) · Zbl 0763.90085 · doi:10.1016/0167-6377(92)90007-P |
| [16] | Marx, D.: Parameterized complexity and approximation algorithms. Comput. J. 51(1), 60-78 (2008) · doi:10.1093/comjnl/bxm048 |
| [17] | Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and its Applications, Oxford University Press, Oxford (2006) · Zbl 1095.68038 |
| [18] | Schoone, A.A., Bodlaender, H.L., van Leeuwen, J.: Diameter increase caused by edge deletion. J. Graph Theory 11, 409-427 (1997) · Zbl 0646.05038 · doi:10.1002/jgt.3190110315 |
| [19] | Vazirani, V.V.: Approximation Algorithms. Springer, Berlin (2001) · Zbl 0999.68546 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
