IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v23y2012i1d10.1007_s10878-010-9338-2.html
   My bibliography  Save this article

Combinatorial algorithms for the maximum k-plex problem

Author

Listed:
  • Benjamin McClosky

    (Rice University)

  • Illya V. Hicks

    (Rice University)

Abstract

The maximum clique problem provides a classic framework for detecting cohesive subgraphs. However, this approach can fail to detect much of the cohesive structure in a graph. To address this issue, Seidman and Foster introduced k-plexes as a degree-based clique relaxation. More recently, Balasundaram et al. formulated the maximum k-plex problem as an integer program and designed a branch-and-cut algorithm. This paper derives a new upper bound on the cardinality of k-plexes and adapts combinatorial clique algorithms to find maximum k-plexes.

Suggested Citation

  • 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.
    • Handle: RePEc:spr:jcomop:v:23:y:2012:i:1:d:10.1007_s10878-010-9338-2
    DOI: 10.1007/s10878-010-9338-2
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-010-9338-2
    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-010-9338-2?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. Stanislav Busygin & Sergiy Butenko & Panos M. Pardalos, 2002. "A Heuristic for the Maximum Independent Set Problem Based on Optimization of a Quadratic Over a Sphere," Journal of Combinatorial Optimization, Springer, vol. 6(3), pages 287-297, September.
    2. E. C. Sewell, 1998. "A Branch and Bound Algorithm for the Stability Number of a Sparse Graph," INFORMS Journal on Computing, INFORMS, vol. 10(4), pages 438-447, November.
    3. 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. 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.
    2. 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.
    3. 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.
    4. Wayne Pullan, 2021. "Local search for the maximum k-plex problem," Journal of Heuristics, Springer, vol. 27(3), pages 303-324, 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. 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.
    2. 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.
    3. Stefano Coniglio & Stefano Gualandi, 2022. "Optimizing over the Closure of Rank Inequalities with a Small Right-Hand Side for the Maximum Stable Set Problem via Bilevel Programming," INFORMS Journal on Computing, INFORMS, vol. 34(2), pages 1006-1023, March.
    4. Foad Mahdavi Pajouh, 2020. "Minimum cost edge blocker clique problem," Annals of Operations Research, Springer, vol. 294(1), pages 345-376, November.
    5. 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.
    6. Veremyev, Alexander & Boginski, Vladimir & Pasiliao, Eduardo L. & Prokopyev, Oleg A., 2022. "On integer programming models for the maximum 2-club problem and its robust generalizations in sparse graphs," European Journal of Operational Research, Elsevier, vol. 297(1), pages 86-101.
    7. San Segundo, Pablo & Coniglio, Stefano & Furini, Fabio & Ljubić, Ivana, 2019. "A new branch-and-bound algorithm for the maximum edge-weighted clique problem," European Journal of Operational Research, Elsevier, vol. 278(1), pages 76-90.
    8. Nasirian, Farzaneh & Mahdavi Pajouh, Foad & Balasundaram, Balabhaskar, 2020. "Detecting a most closeness-central clique in complex networks," European Journal of Operational Research, Elsevier, vol. 283(2), pages 461-475.
    9. 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.
    10. Li, Chu-Min & Liu, Yanli & Jiang, Hua & Manyà, Felip & Li, Yu, 2018. "A new upper bound for the maximum weight clique problem," European Journal of Operational Research, Elsevier, vol. 270(1), pages 66-77.
    11. B. McClosky & S. D. Tanksley, 2013. "Optimizing Experimental Design in Genetics," Journal of Optimization Theory and Applications, Springer, vol. 157(2), pages 520-532, May.
    12. 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.
    13. 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.
    14. Kristjan Reba & Matej Guid & Kati Rozman & Dušanka Janežič & Janez Konc, 2021. "Exact Maximum Clique Algorithm for Different Graph Types Using Machine Learning," Mathematics, MDPI, vol. 10(1), pages 1-14, December.
    15. Lasse Kiviluoto & Patric R. J. Östergård & Vesa P. Vaskelainen, 2016. "Algorithms for finding maximum transitive subtournaments," Journal of Combinatorial Optimization, Springer, vol. 31(2), pages 802-814, February.
    16. Almeida, Maria Teresa & Carvalho, Filipa D., 2014. "An analytical comparison of the LP relaxations of integer models for the k-club problem," European Journal of Operational Research, Elsevier, vol. 232(3), pages 489-498.
    17. Matsypura, Dmytro & Veremyev, Alexander & Pasiliao, Eduardo L. & Prokopyev, Oleg A., 2023. "Finding the most degree-central walks and paths in a graph: Exact and heuristic approaches," European Journal of Operational Research, Elsevier, vol. 308(3), pages 1021-1036.
    18. Anurag Verma & Austin Buchanan & Sergiy Butenko, 2015. "Solving the Maximum Clique and Vertex Coloring Problems on Very Large Sparse Networks," INFORMS Journal on Computing, INFORMS, vol. 27(1), pages 164-177, February.
    19. 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.
    20. 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.

    More about this item

    Keywords

    k-plex; Clique; Coloring;
    All these keywords.

    Statistics

    Access and download statistics

    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:23:y:2012:i:1:d:10.1007_s10878-010-9338-2. 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.