Abstract
In this work we consider the problem of finding Hamilton Cycles in graphs derived from the uniform random intersection graphs model G n, m, p . In particular, (a) for the case m = n α, α> 1 we give a result that allows us to apply (with the same probability of success) any algorithm that finds a Hamilton cycle with high probability in a G n, k graph (i.e. a graph chosen equiprobably form the space of all graphs with k edges), (b) we give an expected polynomial time algorithm for the case p = constant and \(m \leq \alpha {\sqrt{{n}\over {{\rm log}n}}}\) for some constant α, and (c) we show that the greedy approach still works well even in the case \(m = o({{n}\over{{\rm log}n}})\) and p just above the connectivity threshold of G n, m, p (found in [21]) by giving a greedy algorithm that finds a Hamilton cycle in those ranges of m, p with high probability.
This work has been partially supported by the IST Programme of the European Union under contract number 001907 (DELIS) and by the GSRT PENED 2003 ALGO.D.E.S. Project.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alon, N., Spencer, J.H.: The Probabilistic Method, 2nd edn. John Wiley & Sons, Inc., Chichester (2000)
Beier, R., Vöcking, B.: Random Knapsack in Expected Polynomial Time. In: The Proc. of the 35th Annual ACM Symposium on Theory of Computing, pp. 232–241. ACM Press, New York (2003)
Bollobás, B.: Random Graphs, 2nd edn. Cambridge University Press, Cambridge (2001)
Bollobás, B., Fenner, T.I., Frieze, A.M.: An algorithm for Finding Hamilton Paths and Cycles in Random Graphs. Combinatorica 7, 327–341
Coja-Oghlan, A., Taraz, A.: Colouring Random Graphs in Expected Polynomial Time. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol. 2607, pp. 487–498. Springer, Heidelberg (2003)
Díaz, J., Penrose, M.D., Petit, J., Serna, M.: Approximating Layout Problems on Random Geometric Graphs. Journal of Algorithms 39, 78–116 (2001)
Díaz, J., Petit, J., Serna, M.: A Random Graph Model for Optical Networks of Sensors. In: The 1st International Workshop on Efficient and Experimental Algorithms, WEA (2003); Also in the IEEE Transactions on Mobile Computing Journal 2(3), 186–196 (2003)
Díaz, J., Petit, J., Serna, M.: Random Geometric Problems on [0, 1]2. In: Rolim, J.D.P., Serna, M., Luby, M. (eds.) RANDOM 1998. LNCS, vol. 1518, pp. 294–306. Springer, Heidelberg (1998)
Efthymiou, H., Spirakis, P.: On the Existence of Hamiltonian Cycles in Random Intersection Graphs. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 690–701. Springer, Heidelberg (2005)
Fill, J.A., Sheinerman, E.R., Singer-Cohen, K.B.: Random Intersection Graphs when m = ω(n): An Equivalence Theorem Relating the Evolution of the G(n, m, p) and G(n, p) models, http://citeseer.nj.nec.com/fill98random.html
Godehardt, E., Jaworski, J.: Two models of Random Intersection Graphs for Classification. In: Opitz, O., Schwaiger, M. (eds.) Studies in Classification, Data Analysis and Knowledge Organisation, pp. 67–82. Springer, Heidelberg (2002)
Gurevich, Y., Shelah, S.: Expected Computation Time for Hamiltonian Path Problem. SIAM Journal on Computing 16, 486–502 (1987)
Karoński, M., Scheinerman, E.R., Singer- Cohen, K.B.: On Random Intersection Graphs: The Subgraph Problem. Combinatorics, Probability and Computing journal 8, 131–159 (1999)
Marczewski, E.: Sur deux propriétés des classes d’ ensembles. Fund. Math. 33, 303–307 (1945)
Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)
Nikoletseas, S., Palem, K., Spirakis, P., Yung, M.: Short Vertex Disjoint Paths and Multiconnectivity in Random Graphs: Reliable Network Computing. In: Shamir, E., Abiteboul, S. (eds.) ICALP 1994. LNCS, vol. 820, pp. 247–262. Springer, Heidelberg (1994)
Nikoletseas, S., Raptopoulos, C., Spirakis, P.: The Existence and Efficient Construction of Large Independent Sets in General Random Intersection Graphs. In: Díaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 1029–1040. Springer, Heidelberg (2004)
Nikoletseas, S., Spirakis, P.: Expander Properties in Random Regular Graphs with Edge Faults. In: Mayr, E.W., Puech, C. (eds.) STACS 1995. LNCS, vol. 900, pp. 421–432. Springer, Heidelberg (1995)
Penrose, M.: Random Geometric Graphs. Oxford Studies in Probability (2003)
Raptopoulos, C., Spirakis, P.: Simple and Efficient Greedy Algorithms for Hamilton Cycles in Random Intersection Graphs. In: Deng, X., Du, D.-Z. (eds.) ISAAC 2005. LNCS, vol. 3827, pp. 493–504. Springer, Heidelberg (2005), http://students.ceid.upatras.gr/~raptopox/fullpaper.ps
Singer-Cohen, K.B.: Random Intersection Graphs. PhD thesis, John Hopkins University (1995)
Thomason, A.: A simple linear expected time algorithm for the Hamilton cycle problem. Discrete Math. 75, 373–379 (1989)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Raptopoulos, C., Spirakis, P. (2005). Simple and Efficient Greedy Algorithms for Hamilton Cycles in Random Intersection Graphs. In: Deng, X., Du, DZ. (eds) Algorithms and Computation. ISAAC 2005. Lecture Notes in Computer Science, vol 3827. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11602613_50
Download citation
DOI: https://doi.org/10.1007/11602613_50
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-30935-2
Online ISBN: 978-3-540-32426-3
eBook Packages: Computer ScienceComputer Science (R0)