Abstract
We introduce the problem of finding the largest subgraph of a given weighted undirected graph (host graph), subject to constraints on the maximum degree and the diameter. We discuss some applications in security, network design and parallel processing, and in connection with the latter we derive some bounds for the order of the largest subgraph in host graphs of practical interest: the mesh and the hypercube. We also present a heuristic strategy to solve the problem, and we prove an approximation ratio for the algorithm. Finally, we provide some experimental results with a variety of host networks, which show that the algorithm performs better in practice than the prediction provided by our theoretical approximation ratio.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Amini, O., Peleg, D., Perennes, S., Sau, I., Saurabh, S.: Degree-constrained subgraph problems: hardness and approximation results. In: Procs. ALGO-WAOA, 2008. LNCS, vol. 5426, pp. 29–42 (2008)
Asahiro, Y., Miyano, E., Samizo, K.: Approximating maximum diameter-bounded subgraphs. In: Procs. LATIN, 2010. LNCS, vol. 6034, pp. 615–626 (2010)
Barabási, A.-L., Albert, R.: Emergence of scaling in random networks. Science 286, 509–512 (1999)
Barabási, A.-L.: Linked: The New Science of Networks. Perseus Publishing (2002)
Cohen, G., Honkala, I., Litsyn, S., Lobstein, A.: Covering Codes. Elsevier, Amsterdam (1997)
Dekker, A., Colbert, B.: Network robustness and graph topology. In: Procs. 27th Australasian Comp. Science Conf., CRPIT, vol. 26, pp. 359–368 (2004)
Dekker, A.: Simulating network robustness for critical infrastructure networks. In: Procs. 28th Australasian Comp. Science Conf., CRPIT, vol. 38, pp. 59–67 (2005)
Dekker, A., Colbert, B.: The symmetry ratio of a network. In: Procs. 11th Computing: The Australasian Theory Symposium, CRPIT, vol. 41, pp. 13–20 (2005)
Duch, J., Arenas, A.: Community identification using extremal optimization. Phys. Rev. E. 72, 027104 (2005)
Elspas, B.: Topological constraints on interconnection-limited logic. In: Proceedings of the Fifth IEEE Annual Symposium on Switching Circuit Theory and Logical Design, pp. 133–137 (1964)
Exoo, G.: A family of graphs and the degree-diameter problem. J. Graph Theory 37, 118–124 (2001)
Garey, M., Johnson, D.: Computers and Intractability. A Guide to the Theory of NP-completeness. Freeman and Co. (1979)
Johnson, D.: The NP-completeness column: an ongoing guide. J. Algorithms 6, 145–159 (1985)
Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds). Complexity of Computer Computations, pp. 85–103 (1972)
Könemann, J., Levin, A., Sinha, A.: Approximating the degree-bounded minimum diameter spanning tree problem. Algorithmica 41, 117–129 (2005)
Kumar, N.: Bounding the volume of Hamming balls. http://cstheory.wordpress.com/2010/08/13/bounding-the-volume-of-hamming-balls. Accessed Feb 2011
Loz, E., Pérez-Rosés, H., Pineda-Villavicencio, G.: Combinatorics wiki – the degree diameter problem for general graphs. http://combinatoricswiki.org/wiki/The_Degree_Diameter_Problem_for_General_Graphs. Accessed 14 Jan 2012
Loz, E., Pérez-Rosés, H., Pineda-Villavicencio, G.: Combinatorics wiki - MaxDDBS in the mesh. http://combinatoricswiki.org/wiki/MaxDDBS_in_the_mesh. Accessed on 14 Jan 2012
Miller, M., Siran, J.: Moore graphs and beyond: a survey of the degree-diameter problem. Electron. J. Combin., Dynamic Survey 14, 1–61 (2005)
Ravi, R., Marathe, M., Ravi, S., Rosenkrantz, D., Hunt III, H.B.: Approximation algorithms for degree-constrained minimum-cost network-design problems. Algorithmica 1, 58–78 (2001)
Skriganov, M., Sobolev, A.: Variation of the number of lattice points in large balls. Acta Arith. 120, 245–267 (2005)
Sohaee, N., Forst, C.: Bounded diameter clustering scheme for protein interaction networks. In: Procs. World Congress on Engineering and Computer Science, vol. I (2009)
Watts, D.: Six Degrees: The Science of a Connected Age. William Heinemann (2003)
Widmer, M.: Lipschitz Class, Narrow Class, and Counting Lattice Points. Report 2010–13, Graz University of Technology (2010)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Dekker, A., Pérez-Rosés, H., Pineda-Villavicencio, G. et al. The Maximum Degree & Diameter-Bounded Subgraph and its Applications. J Math Model Algor 11, 249–268 (2012). https://doi.org/10.1007/s10852-012-9182-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10852-012-9182-8