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

Partitioning a graph into balanced connected classes: Formulations, separation and experiments

Author

Listed:
  • Miyazawa, Flávio K.
  • Moura, Phablo F.S.
  • Ota, Matheus J.
  • Wakabayashi, Yoshiko

Abstract

This work addresses the balanced connectedk-partition problem (BCPk), which is formally defined as follows. Given a connected graph G=(V,E) with nonnegative weights on the vertices, find a partition {Vi}i=1k of V such that each class Vi induces a connected subgraph of G, and the weight of a class with the minimum weight is as large as possible. This problem, known to be NP-hard, has been largely investigated under different approaches and perspectives: exact algorithms, approximation algorithms for some values of k or special classes of graphs, and inapproximability results. On the practical side, BCPk is used to model many applications arising in image processing, cluster analysis, operating systems and robotics. We propose three linear programming formulations for BCPk. The first one contains only binary variables and a potentially large number of constraints that can be separated in polynomial time in the corresponding linear relaxation. We introduce new valid inequalities and design polynomial-time separation algorithms for them. The other two formulations are based on flows and have a polynomial number of constraints and variables. Our computational experiments show that the exact algorithms based on the proposed formulations outperform the other exact approaches presented in the literature.

Suggested Citation

  • Miyazawa, Flávio K. & Moura, Phablo F.S. & Ota, Matheus J. & Wakabayashi, Yoshiko, 2021. "Partitioning a graph into balanced connected classes: Formulations, separation and experiments," European Journal of Operational Research, Elsevier, vol. 293(3), pages 826-836.
    • Handle: RePEc:eee:ejores:v:293:y:2021:i:3:p:826-836
    DOI: 10.1016/j.ejor.2020.12.059
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221720311218
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2020.12.059?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. Maravalle, Maurizio & Simeone, Bruno & Naldini, Rosella, 1997. "Clustering on trees," Computational Statistics & Data Analysis, Elsevier, vol. 24(2), pages 217-234, April.
    2. Boeing, Geoff, 2017. "OSMnx: New Methods for Acquiring, Constructing, Analyzing, and Visualizing Complex Street Networks," SocArXiv q86sd, Center for Open Science.
    3. Guangting Chen & Yong Chen & Zhi-Zhong Chen & Guohui Lin & Tian Liu & An Zhang, 0. "Approximation algorithms for the maximally balanced connected graph tripartition problem," Journal of Combinatorial Optimization, Springer, vol. 0, pages 1-21.
    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. Alexandre Xavier Ywata Carvalho & Pedro Henrique Melo Albuquerque & Gilberto Rezende de Almeida Junior & Rafael Dantas Guimarães & Camilo Rey Laureto, 2009. "Clusterização Hierárquica Espacial com Atributos Binários," Discussion Papers 1428, Instituto de Pesquisa Econômica Aplicada - IPEA.
    2. Matteo Böhm & Mirco Nanni & Luca Pappalardo, 2022. "Gross polluters and vehicle emissions reduction," Nature Sustainability, Nature, vol. 5(8), pages 699-707, August.
    3. Lorenzo Barbieri & Roberto D’Autilia & Paola Marrone & Ilaria Montella, 2023. "Graph Representation of the 15-Minute City: A Comparison between Rome, London, and Paris," Sustainability, MDPI, vol. 15(4), pages 1-14, February.
    4. Ospina, Juan P. & Duque, Juan C. & Botero-Fernández, Verónica & Montoya, Alejandro, 2022. "The maximal covering bicycle network design problem," Transportation Research Part A: Policy and Practice, Elsevier, vol. 159(C), pages 222-236.
    5. Brinkley, Catherine & Raj, Subhashni, 2022. "Perfusion and urban thickness: The shape of cities," Land Use Policy, Elsevier, vol. 115(C).
    6. Alves d'Acampora, Bárbara Heliodora & Maraschin, Clarice & Taufemback, Cleiton Guollo, 2023. "Landscape ecology and urban spatial configuration: Exploring a methodological relationship. Application in Pelotas, Brazil," Ecological Modelling, Elsevier, vol. 486(C).
    7. Ponce, Diego & Puerto, Justo & Temprano, Francisco, 2024. "Mixed-integer linear programming formulations and column generation algorithms for the Minimum Normalized Cuts problem on networks," European Journal of Operational Research, Elsevier, vol. 316(2), pages 519-538.
    8. Ali Enes Dingil & Federico Rupi & Joerg Schweizer & Zaneta Stasiskiene & Kasra Aalipour, 2019. "The Role of Culture in Urban Travel Patterns: Quantitative Analyses of Urban Areas Based on Hofstede’s Culture Dimensions," Social Sciences, MDPI, vol. 8(8), pages 1-12, July.
    9. Geoff Boeing, 2020. "Urban Street Network Analysis in a Computational Notebook," REGION, European Regional Science Association, vol. 7, pages 39-51.
    10. Geoff Boeing, 2020. "A multi-scale analysis of 27,000 urban street networks: Every US city, town, urbanized area, and Zillow neighborhood," Environment and Planning B, , vol. 47(4), pages 590-608, May.
    11. Lin, Jie & Cromley, Gordon, 2023. "Using the transportation problem to build a congestion/threshold constrained spatial accessibility model," Journal of Transport Geography, Elsevier, vol. 112(C).
    12. Waddell, Paul & Boeing, Geoff & Gardner, Max & Porter, Emily, 2018. "An Integrated Pipeline Architecture for Modeling Urban Land Use, Travel Demand, and Traffic Assignment," SocArXiv 74zaw, Center for Open Science.
    13. Shang, Wen-Long & Chen, Jinyu & Bi, Huibo & Sui, Yi & Chen, Yanyan & Yu, Haitao, 2021. "Impacts of COVID-19 pandemic on user behaviors and environmental benefits of bike sharing: A big-data analysis," Applied Energy, Elsevier, vol. 285(C).
    14. Geoff Boeing, 2020. "Planarity and street network representation in urban form analysis," Environment and Planning B, , vol. 47(5), pages 855-869, June.
    15. Geoff Boeing & Yougeng Lu & Clemens Pilgram, 2023. "Local inequities in the relative production of and exposure to vehicular air pollution in Los Angeles," Urban Studies, Urban Studies Journal Limited, vol. 60(12), pages 2351-2368, September.
    16. Leonardo Barleta & Mateo Carrillo & Zephyr Frank & Erik Steiner, 2020. "Ejidos, Urbanization, and the Production of Inequality in Formerly Agricultural Lands, Guadalajara, Mexico, 1975–2020," Land, MDPI, vol. 9(12), pages 1-21, December.
    17. Juan C Duque & Nancy Lozano-Gracia & Jorge E Patino & Paula Restrepo, 2022. "Urban form and productivity: What shapes are Latin-American cities?," Environment and Planning B, , vol. 49(1), pages 131-150, January.
    18. Jari Vepsäläinen, 2022. "Energy Demand Analysis and Powertrain Design of a High-Speed Delivery Robot Using Synthetic Driving Cycles," Energies, MDPI, vol. 15(6), pages 1-21, March.
    19. Zhang, Hui & Zhan, Bo & Ouyang, Min, 2024. "Enhancing accessibility through rail transit in congested urban areas: A cross-regional analysis," Journal of Transport Geography, Elsevier, vol. 115(C).
    20. Luxiao Yang & Qizhi Jin & Feng Fu, 2024. "Research on Urban Street Network Structure Based on Spatial Syntax and POI Data," Sustainability, MDPI, vol. 16(5), pages 1-22, February.

    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:293:y:2021:i:3:p:826-836. 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.