Minimizing cyclic cutwidth of graphs using a memetic algorithm

Pallavi Jain (), Kamal Srivastava () and Gur Saran ()
Additional contact information
Pallavi Jain: Dayalbagh Educational Institute
Kamal Srivastava: Dayalbagh Educational Institute
Gur Saran: Dayalbagh Educational Institute

Journal of Heuristics, 2016, vol. 22, issue 6, No 2, 815-848

Abstract: Abstract Cyclic cutwidth minimization problem (CCMP) consists of embedding a graph onto a circle such that the maximum cutwidth in a region is minimized. It is an NP-complete problem and for some classes of graphs, exact results of cyclic cutwidth have been proved in literature. However, no algorithm has been reported for general graphs. In this paper, a memetic algorithm is proposed for CCMP in which we have designed six construction heuristics in order to generate a good initial population and also local search is employed to improve the solutions in each generational phase. The algorithm achieves optimal results for the classes of graphs with known exact results. Extensive experiments have also been conducted on some classes of graphs for which exact results are not known such as the complete split graph, join of hypercubes, toroidal meshes, cone graph and some instances of Harwell-Boeing graphs which are a subset of public domain Matrix Market library. Trends observed in the experimental results for some of the classes of graphs have led to conjectures for cyclic cutwidth.

Keywords: Cyclic cutwidth; Memetic algorithm; Graph layout problems (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10732-016-9319-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:joheur:v:22:y:2016:i:6:d:10.1007_s10732-016-9319-4

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-016-9319-4

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().