IDEAS home Printed from https://ideas.repec.org/a/spr/joheur/v27y2021i3d10.1007_s10732-020-09459-5.html
   My bibliography  Save this article

Local search for the maximum k-plex problem

Author

Listed:
  • Wayne Pullan

    (Griffith University)

Abstract

The maximum k-plex problem is an important, computationally complex graph based problem. In this study an effective k-plex local search (KLS) is presented for solving this problem on a wide range of graph types. KLS uses data structures suitable for the graph being analysed and has mechanisms for preventing search cycling and promoting search diversity. State of the art results were obtained on 121 dense graphs and 61 large real-life (sparse) graphs. Comparisons with three recent algorithms on the more difficult graphs show that KLS performed better or as well as in 93% of 332 significant k-plex problem instances investigated achieving either larger average k-plex sizes (including some new results) or, when these were equivalent, lower CPU requirements.

Suggested Citation

  • Wayne Pullan, 2021. "Local search for the maximum k-plex problem," Journal of Heuristics, Springer, vol. 27(3), pages 303-324, June.
    • Handle: RePEc:spr:joheur:v:27:y:2021:i:3:d:10.1007_s10732-020-09459-5
    DOI: 10.1007/s10732-020-09459-5
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10732-020-09459-5
    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/s10732-020-09459-5?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. Balabhaskar Balasundaram & Sergiy Butenko & Illya V. Hicks, 2011. "Clique Relaxations in Social Network Analysis: The Maximum k -Plex Problem," Operations Research, INFORMS, vol. 59(1), pages 133-142, February.
    2. Hannes Moser & Rolf Niedermeier & Manuel Sorge, 2012. "Exact combinatorial algorithms and experiments for finding maximum k-plexes," Journal of Combinatorial Optimization, Springer, vol. 24(3), pages 347-373, October.
    3. 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.
    4. Benjamin McClosky & Illya V. Hicks, 2012. "Combinatorial algorithms for the maximum k-plex problem," Journal of Combinatorial Optimization, Springer, vol. 23(1), pages 29-49, January.
    Full references (including those not matched with items on IDEAS)

    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. Bruno Nogueira & Rian G. S. Pinheiro, 2020. "A GPU based local search algorithm for the unweighted and weighted maximum s-plex problems," Annals of Operations Research, Springer, vol. 284(1), pages 367-400, January.
    2. 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.
    3. Zhuqi Miao & Balabhaskar Balasundaram, 2020. "An Ellipsoidal Bounding Scheme for the Quasi-Clique Number of a Graph," INFORMS Journal on Computing, INFORMS, vol. 32(3), pages 763-778, July.
    4. Timo Gschwind & Stefan Irnich & Fabio Furini & Roberto Wolfler Calvo, 2021. "A Branch-and-Price Framework for Decomposing Graphs into Relaxed Cliques," INFORMS Journal on Computing, INFORMS, vol. 33(3), pages 1070-1090, July.
    5. Timo Gschwind & Stefan Irnich & Fabio Furini & Roberto Wolfler Calvo, 2017. "A Branch-and-Price Framework for Decomposing Graphs into Relaxed Cliques," Working Papers 1723, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    6. Timo Gschwind & Stefan Irnich & Fabio Furini & Roberto Wolfler Calvo, 2017. "Social Network Analysis and Community Detection by Decomposing a Graph into Relaxed Cliques," Working Papers 1722, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    7. 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.
    8. François Fulconis & Didier Bédé & Laurence Saglietto & Joice de Almeira Goes & Gilles Paché & Raymundo Forradelas, 2014. "The entry of logistics service provider (LSP) into the wine industry supply chain," Post-Print hal-01062817, HAL.
    9. Benjamin McClosky & John D. Arellano & Illya V. Hicks, 2015. "Co-2-plex vertex partitions," Journal of Combinatorial Optimization, Springer, vol. 30(3), pages 729-746, October.
    10. Filipa D. Carvalho & Maria Teresa Almeida, 2017. "The triangle k-club problem," Journal of Combinatorial Optimization, Springer, vol. 33(3), pages 814-846, April.
    11. Maciej Rysz & Mohammad Mirghorbani & Pavlo Krokhmal & Eduardo L. Pasiliao, 2014. "On risk-averse maximum weighted subgraph problems," Journal of Combinatorial Optimization, Springer, vol. 28(1), pages 167-185, July.
    12. Zhou, Yi & Rossi, André & Hao, Jin-Kao, 2018. "Towards effective exact methods for the Maximum Balanced Biclique Problem in bipartite graphs," European Journal of Operational Research, Elsevier, vol. 269(3), pages 834-843.
    13. Timo Gschwind & Stefan Irnich & Isabel Podlinski, 2015. "Maximum Weight Relaxed Cliques and Russian Doll Search Revisited," Working Papers 1504, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz, revised 19 May 2015.
    14. Şuvak, Zeynep & Altınel, İ. Kuban & Aras, Necati, 2020. "Exact solution algorithms for the maximum flow problem with additional conflict constraints," European Journal of Operational Research, Elsevier, vol. 287(2), pages 410-437.
    15. Zeynep Ertem & Eugene Lykhovyd & Yiming Wang & Sergiy Butenko, 2020. "The maximum independent union of cliques problem: complexity and exact approaches," Journal of Global Optimization, Springer, vol. 76(3), pages 545-562, March.
    16. Maciej Rysz & Foad Mahdavi Pajouh & Pavlo Krokhmal & Eduardo L. Pasiliao, 2018. "Identifying risk-averse low-diameter clusters in graphs with stochastic vertex weights," Annals of Operations Research, Springer, vol. 262(1), pages 89-108, March.
    17. Furini, Fabio & Ljubić, Ivana & Martin, Sébastien & San Segundo, Pablo, 2019. "The maximum clique interdiction problem," European Journal of Operational Research, Elsevier, vol. 277(1), pages 112-127.
    18. Fu, Wentao & Sun, Yang, 2021. "Rumor investigation in networks," Economic Modelling, Elsevier, vol. 98(C), pages 168-178.
    19. Jianhua Tu & Lidong Wu & Jing Yuan & Lei Cui, 2017. "On the vertex cover $$P_3$$ P 3 problem parameterized by treewidth," Journal of Combinatorial Optimization, Springer, vol. 34(2), pages 414-425, August.
    20. Zhou, Qing & Benlic, Una & Wu, Qinghua, 2020. "An opposition-based memetic algorithm for the maximum quasi-clique problem," European Journal of Operational Research, Elsevier, vol. 286(1), pages 63-83.

    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:joheur:v:27:y:2021:i:3:d:10.1007_s10732-020-09459-5. 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.