IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v27y2014i2d10.1007_s10878-012-9592-6.html
   My bibliography  Save this article

Improvements to MCS algorithm for the maximum clique problem

Author

Listed:
  • Mikhail Batsyn

    (National Research University Higher School of Economics)

  • Boris Goldengorin

    (National Research University Higher School of Economics)

  • Evgeny Maslov

    (National Research University Higher School of Economics)

  • Panos M. Pardalos

    (National Research University Higher School of Economics
    University of Florida)

Abstract

In this paper we present improvements to one of the most recent and fastest branch-and-bound algorithm for the maximum clique problem—MCS algorithm by Tomita et al. (Proceedings of the 4th international conference on Algorithms and Computation, WALCOM’10, pp. 191–203, 2010). The suggested improvements include: incorporating of an efficient heuristic returning a high-quality initial solution, fast detection of clique vertices in a set of candidates, better initial colouring, and avoiding dynamic memory allocation. Our computational study shows some impressive results, mainly we have solved p_hat1000-3 benchmark instance which is intractable for MCS algorithm and got speedups of 7, 3000, and 13000 times for gen400_p0.9_55, gen400_p0.9_65, and gen400_p0.9_75 instances correspondingly.

Suggested Citation

  • Mikhail Batsyn & Boris Goldengorin & Evgeny Maslov & Panos M. Pardalos, 2014. "Improvements to MCS algorithm for the maximum clique problem," Journal of Combinatorial Optimization, Springer, vol. 27(2), pages 397-416, February.
    • Handle: RePEc:spr:jcomop:v:27:y:2014:i:2:d:10.1007_s10878-012-9592-6
    DOI: 10.1007/s10878-012-9592-6
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-012-9592-6
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10878-012-9592-6?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Jenelius, Erik & Petersen, Tom & Mattsson, Lars-Göran, 2006. "Importance and exposure in road network vulnerability analysis," Transportation Research Part A: Policy and Practice, Elsevier, vol. 40(7), pages 537-560, August.
    2. Butenko, S. & Wilhelm, W.E., 2006. "Clique-detection models in computational biochemistry and genomics," European Journal of Operational Research, Elsevier, vol. 173(1), pages 1-17, August.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Sándor Szabó, 2021. "A Clique Search Problem and its Application to Machine Scheduling," SN Operations Research Forum, Springer, vol. 2(4), pages 1-12, December.
    2. Seyedmohammadhossein Hosseinian & Dalila B. M. M. Fontes & Sergiy Butenko, 2020. "A Lagrangian Bound on the Clique Number and an Exact Algorithm for the Maximum Edge Weight Clique Problem," INFORMS Journal on Computing, INFORMS, vol. 32(3), pages 747-762, July.
    3. Seyedmohammadhossein Hosseinian & Dalila B. M. M. Fontes & Sergiy Butenko, 2018. "A nonconvex quadratic optimization approach to the maximum edge weight clique problem," Journal of Global Optimization, Springer, vol. 72(2), pages 219-240, October.
    4. Larisa Komosko & Mikhail Batsyn & Pablo San Segundo & Panos M. Pardalos, 2016. "A fast greedy sequential heuristic for the vertex colouring problem based on bitwise operations," Journal of Combinatorial Optimization, Springer, vol. 31(4), pages 1665-1677, May.
    5. Sebastian Lamm & Peter Sanders & Christian Schulz & Darren Strash & Renato F. Werneck, 2017. "Finding near-optimal independent sets at scale," Journal of Heuristics, Springer, vol. 23(4), pages 207-229, August.
    6. Assif Assad & Kusum Deep, 2018. "A heuristic based harmony search algorithm for maximum clique problem," OPSEARCH, Springer;Operational Research Society of India, vol. 55(2), pages 411-433, June.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Evgeny Maslov & Mikhail Batsyn & Panos Pardalos, 2014. "Speeding up branch and bound algorithms for solving the maximum clique problem," Journal of Global Optimization, Springer, vol. 59(1), pages 1-21, May.
    2. Zhang, Nan & Huang, Hong & Su, Boni & Zhao, Jinlong, 2015. "Analysis of dynamic road risk for pedestrian evacuation," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 430(C), pages 171-183.
    3. Richard Connors & David Watling, 2015. "Assessing the Demand Vulnerability of Equilibrium Traffic Networks via Network Aggregation," Networks and Spatial Economics, Springer, vol. 15(2), pages 367-395, June.
    4. Cats, Oded & Jenelius, Erik, 2015. "Planning for the unexpected: The value of reserve capacity for public transport network robustness," Transportation Research Part A: Policy and Practice, Elsevier, vol. 81(C), pages 47-61.
    5. Mengying Cui & David Levinson, 2018. "Accessibility analysis of risk severity," Transportation, Springer, vol. 45(4), pages 1029-1050, July.
    6. Dowds, Jonathan & Aultman-Hall, Lisa, 2015. "Challenges and Opportunities for Integrating Climate Adaptation Efforts across State, Regional and Local Transportation Agencies," Institute of Transportation Studies, Working Paper Series qt5t88h66m, Institute of Transportation Studies, UC Davis.
    7. Bucar, Raif C.B. & Hayeri, Yeganeh M., 2020. "Quantitative assessment of the impacts of disruptive precipitation on surface transportation," Reliability Engineering and System Safety, Elsevier, vol. 203(C).
    8. Jenelius, Erik, 2010. "User inequity implications of road network vulnerability," The Journal of Transport and Land Use, Center for Transportation Studies, University of Minnesota, vol. 2(3), pages 57-73.
    9. Mohamad Darayi & Kash Barker & Joost R. Santos, 2017. "Component Importance Measures for Multi-Industry Vulnerability of a Freight Transportation Network," Networks and Spatial Economics, Springer, vol. 17(4), pages 1111-1136, December.
    10. Foad Mahdavi Pajouh, 2020. "Minimum cost edge blocker clique problem," Annals of Operations Research, Springer, vol. 294(1), pages 345-376, November.
    11. Svyatoslav Trukhanov & Chitra Balasubramaniam & Balabhaskar Balasundaram & Sergiy Butenko, 2013. "Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations," Computational Optimization and Applications, Springer, vol. 56(1), pages 113-130, September.
    12. Jenelius, Erik & Mattsson, Lars-Göran, 2012. "Road network vulnerability analysis of area-covering disruptions: A grid-based approach with case study," Transportation Research Part A: Policy and Practice, Elsevier, vol. 46(5), pages 746-760.
    13. Zhuqi Miao & Balabhaskar Balasundaram & Eduardo L. Pasiliao, 2014. "An exact algorithm for the maximum probabilistic clique problem," Journal of Combinatorial Optimization, Springer, vol. 28(1), pages 105-120, July.
    14. Almoghathawi, Yasser & Barker, Kash & Rocco, Claudio M. & Nicholson, Charles D., 2017. "A multi-criteria decision analysis approach for importance identification and ranking of network components," Reliability Engineering and System Safety, Elsevier, vol. 158(C), pages 142-151.
    15. Baroud, Hiba & Barker, Kash & Ramirez-Marquez, Jose E. & Rocco S., Claudio M., 2014. "Importance measures for inland waterway network resilience," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 62(C), pages 55-67.
    16. Safirova, Elena & Gillingham, Kenneth & Houde, Sébastien, 2007. "Measuring marginal congestion costs of urban transportation: Do networks matter?," Transportation Research Part A: Policy and Practice, Elsevier, vol. 41(8), pages 734-749, October.
    17. Carvalho, Filipa D. & Almeida, M. Teresa, 2011. "Upper bounds and heuristics for the 2-club problem," European Journal of Operational Research, Elsevier, vol. 210(3), pages 489-494, May.
    18. Tony H. Grubesic & Timothy C. Matisziw, 2008. "Prospects for Assessing and Managing Vulnerable Infrastructures: Policy and Practice," Growth and Change, Wiley Blackwell, vol. 39(4), pages 543-547, December.
    19. Erik Jenelius & Lars-Göran Mattsson, 2011. "The impact of network density, travel and location patterns on regional road network vulnerability," ERSA conference papers ersa10p448, European Regional Science Association.
    20. Zhou, Yi & Lin, Weibo & Hao, Jin-Kao & Xiao, Mingyu & Jin, Yan, 2022. "An effective branch-and-bound algorithm for the maximum s-bundle problem," European Journal of Operational Research, Elsevier, vol. 297(1), pages 27-39.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jcomop:v:27:y:2014:i:2:d:10.1007_s10878-012-9592-6. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.