An algorithm and upper bounds for the weighted maximal planar graph problem

Amir Ahmadi-Javid, Amir Ardestani-Jaafari, Leslie R Foulds, Hossein Hojabri and Reza Zanjirani Farahani
Additional contact information
Amir Ahmadi-Javid: Amirkabir University of Technology, Tehran, Iran
Amir Ardestani-Jaafari: GERAD, HEC Montréal, Montréal, Canada
Leslie R Foulds: Instituto de Informática, Universidade Federal de Goiás, Goiania, Brasil
Hossein Hojabri: CIRRELT and Départment d’informatique et de recherche opérationnelle, Université de Montréal, Montréal, Canada
Reza Zanjirani Farahani: Kingston University, London, UK

Journal of the Operational Research Society, 2015, vol. 66, issue 8, 1399-1412

Abstract: In this paper, we investigate the weighted maximal planar graph (WMPG) problem. Given a complete, edge-weighted, simple graph, the WMPG problem involves finding a subgraph with the highest sum of edge weights that is maximal planar, namely, it can be embedded in the plane without any of its edges intersecting, and no additional edge can be added to the subgraph without violating its planarity. We present a new integer linear programming (ILP) model for this problem. We then develop a cutting-plane algorithm to solve the WMPG problem based on the proposed ILP model. This algorithm enables the problem to be solved more efficiently than previously reported algorithms. New upper bounds are also provided, which are useful in evaluating the quality of heuristic solutions or in generating initial solutions for meta-heuristics. Computational results are reported for a set of 417 test instances of size varying from 6 to 100 nodes including 105 instances from the literature and 312 randomly generated instances. The computational results indicate that instances with up to 24 nodes can be solved optimally in reasonable computational time and the new upper bounds for larger instances significantly improve existing upper bounds.

Date: 2015
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.palgrave-journals.com/jors/journal/v66/n8/pdf/jors201498a.pdf Link to full text PDF (application/pdf)
http://www.palgrave-journals.com/jors/journal/v66/n8/full/jors201498a.html Link to full text HTML (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:pal:jorsoc:v:66:y:2015:i:8:p:1399-1412

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/41274

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald and Jonathan Crook

More articles in Journal of the Operational Research Society from Palgrave Macmillan, The OR Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().