IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v138y2002i1p21-28.html
   My bibliography  Save this article

An exact algorithm for the maximum k-club problem in an undirected graph

Author

Listed:
  • Bourjolly, Jean-Marie
  • Laporte, Gilbert
  • Pesant, Gilles

Abstract

No abstract is available for this item.

Suggested Citation

  • Bourjolly, Jean-Marie & Laporte, Gilbert & Pesant, Gilles, 2002. "An exact algorithm for the maximum k-club problem in an undirected graph," European Journal of Operational Research, Elsevier, vol. 138(1), pages 21-28, April.
    • Handle: RePEc:eee:ejores:v:138:y:2002:i:1:p:21-28
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(01)00133-3
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    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. Robert Mokken, 1979. "Cliques, clubs and clans," Quality & Quantity: International Journal of Methodology, Springer, vol. 13(2), pages 161-173, April.
    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. Filipa D. Carvalho & Maria Teresa Almeida, 2017. "The triangle k-club problem," Journal of Combinatorial Optimization, Springer, vol. 33(3), pages 814-846, April.
    2. 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.
    3. Wu, Qinghua & Hao, Jin-Kao, 2015. "A review on algorithms for maximum clique problems," European Journal of Operational Research, Elsevier, vol. 242(3), pages 693-709.
    4. Komusiewicz, Christian & Nichterlein, André & Niedermeier, Rolf & Picker, Marten, 2019. "Exact algorithms for finding well-connected 2-clubs in sparse real-world graphs: Theory and experiments," European Journal of Operational Research, Elsevier, vol. 275(3), pages 846-864.
    5. Oleksandra Yezerska & Foad Mahdavi Pajouh & Alexander Veremyev & Sergiy Butenko, 2019. "Exact algorithms for the minimum s-club partitioning problem," Annals of Operations Research, Springer, vol. 276(1), pages 267-291, May.
    6. Shahram Shahinpour & Sergiy Butenko, 2013. "Algorithms for the maximum k-club problem in graphs," Journal of Combinatorial Optimization, Springer, vol. 26(3), pages 520-554, October.
    7. Buchanan, Austin & Sung, Je Sang & Boginski, Vladimir & Butenko, Sergiy, 2014. "On connected dominating sets of restricted diameter," European Journal of Operational Research, Elsevier, vol. 236(2), pages 410-418.
    8. Veremyev, Alexander & Boginski, Vladimir, 2012. "Identifying large robust network clusters via new compact formulations of maximum k-club problems," European Journal of Operational Research, Elsevier, vol. 218(2), pages 316-326.
    9. 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.
    10. Riccardo Dondi & Mohammad Mehdi Hosseinzadeh & Giancarlo Mauri & Italo Zoppis, 2021. "Top-k overlapping densest subgraphs: approximation algorithms and computational complexity," Journal of Combinatorial Optimization, Springer, vol. 41(1), pages 80-104, January.
    11. 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.
    12. Balasundaram, Balabhaskar & Borrero, Juan S. & Pan, Hao, 2022. "Graph signatures: Identification and optimization," European Journal of Operational Research, Elsevier, vol. 296(3), pages 764-775.
    13. 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.
    14. 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.
    15. 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.
    16. Yajun Lu & Hosseinali Salemi & Balabhaskar Balasundaram & Austin Buchanan, 2022. "On Fault-Tolerant Low-Diameter Clusters in Graphs," INFORMS Journal on Computing, INFORMS, vol. 34(6), pages 3181-3199, November.
    17. Alexander Veremyev & Vladimir Boginski & Eduardo Pasiliao, 2015. "Analytical characterizations of some classes of optimal strongly attack-tolerant networks and their Laplacian spectra," Journal of Global Optimization, Springer, vol. 61(1), pages 109-138, January.
    18. Foad Mahdavi Pajouh & Esmaeel Moradi & Balabhaskar Balasundaram, 2017. "Detecting large risk-averse 2-clubs in graphs with random edge failures," Annals of Operations Research, Springer, vol. 249(1), pages 55-73, February.
    19. Yezerska, Oleksandra & Mahdavi Pajouh, Foad & Butenko, Sergiy, 2017. "On biconnected and fragile subgraphs of low diameter," European Journal of Operational Research, Elsevier, vol. 263(2), pages 390-400.
    20. Foad Mahdavi Pajouh & Balabhaskar Balasundaram & Illya V. Hicks, 2016. "On the 2-Club Polytope of Graphs," Operations Research, INFORMS, vol. 64(6), pages 1466-1481, December.
    21. 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.
    22. Timo Gschwind & Stefan Irnich & Fabio Furini & Roberto Wol?er Calvo, 2015. "Social Network Analysis and Community Detection by Decomposing a Graph into Relaxed Cliques," Working Papers 1520, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.

    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. Grigory Pastukhov & Alexander Veremyev & Vladimir Boginski & Eduardo L. Pasiliao, 2014. "Optimal design and augmentation of strongly attack-tolerant two-hop clusters in directed networks," Journal of Combinatorial Optimization, Springer, vol. 27(3), pages 462-486, April.
    2. 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.
    3. Komusiewicz, Christian & Nichterlein, André & Niedermeier, Rolf & Picker, Marten, 2019. "Exact algorithms for finding well-connected 2-clubs in sparse real-world graphs: Theory and experiments," European Journal of Operational Research, Elsevier, vol. 275(3), pages 846-864.
    4. Filipa D. Carvalho & Maria Teresa Almeida, 2017. "The triangle k-club problem," Journal of Combinatorial Optimization, Springer, vol. 33(3), pages 814-846, April.
    5. Riccardo Dondi & Mohammad Mehdi Hosseinzadeh & Giancarlo Mauri & Italo Zoppis, 2021. "Top-k overlapping densest subgraphs: approximation algorithms and computational complexity," Journal of Combinatorial Optimization, Springer, vol. 41(1), pages 80-104, January.
    6. Seiler, A. & Papanagnou, C. & Scarf, P., 2020. "On the relationship between financial performance and position of businesses in supply chain networks," International Journal of Production Economics, Elsevier, vol. 227(C).
    7. Vincent Labatut & Jean-Michel Balasque, 2012. "Detection and Interpretation of Communities in Complex Networks: Methods and Practical Application," Post-Print hal-00633653, HAL.
    8. 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.
    9. 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.
    10. Buchanan, Austin & Sung, Je Sang & Boginski, Vladimir & Butenko, Sergiy, 2014. "On connected dominating sets of restricted diameter," European Journal of Operational Research, Elsevier, vol. 236(2), pages 410-418.
    11. 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.
    12. George, Varghese P. & Allen, Thomas J. 1931-, 1993. "Relational data in organzational settings : an introductory note for using AGNI and netgraphs to analyze nodes, relationships, partitions and boundaries," Working papers #85-93. Working paper (Sl, Massachusetts Institute of Technology (MIT), Sloan School of Management.
    13. 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.
    14. Sungchul Choi & Janghyeok Yoon & Kwangsoo Kim & Jae Yeol Lee & Cheol-Han Kim, 2011. "SAO network analysis of patents for technology trends identification: a case study of polymer electrolyte membrane technology in proton exchange membrane fuel cells," Scientometrics, Springer;Akadémiai Kiadó, vol. 88(3), pages 863-883, September.
    15. 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.
    16. Oleksandra Yezerska & Foad Mahdavi Pajouh & Alexander Veremyev & Sergiy Butenko, 2019. "Exact algorithms for the minimum s-club partitioning problem," Annals of Operations Research, Springer, vol. 276(1), pages 267-291, May.
    17. Veremyev, Alexander & Boginski, Vladimir, 2012. "Identifying large robust network clusters via new compact formulations of maximum k-club problems," European Journal of Operational Research, Elsevier, vol. 218(2), pages 316-326.
    18. Alexander Veremyev & Vladimir Boginski & Eduardo Pasiliao, 2015. "Analytical characterizations of some classes of optimal strongly attack-tolerant networks and their Laplacian spectra," Journal of Global Optimization, Springer, vol. 61(1), pages 109-138, January.
    19. Foad Mahdavi Pajouh & Balabhaskar Balasundaram & Illya V. Hicks, 2016. "On the 2-Club Polytope of Graphs," Operations Research, INFORMS, vol. 64(6), pages 1466-1481, December.
    20. Yezerska, Oleksandra & Mahdavi Pajouh, Foad & Butenko, Sergiy, 2017. "On biconnected and fragile subgraphs of low diameter," European Journal of Operational Research, Elsevier, vol. 263(2), pages 390-400.

    More about this item

    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:eee:ejores:v:138:y:2002:i:1:p:21-28. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.