GraphCombEx: A Software Tool for Exploration of Combinatorial Optimisation Properties of Large Graphs

David Chalupa, Ken Hawick

Research output: Contribution to journalJournal articleResearchpeer-review

Abstract

We present a prototype of a software tool for exploration of multiple combinatorial optimisation problems in large real-world and synthetic complex networks. Our tool, called GraphCombEx (an acronym of Graph Combinatorial Explorer), provides a unified framework for scalable computation of high-quality suboptimal solutions and bounds for a number of widely studied combinatorial optimisation problems in large graphs. The problems currently supported include: maximum clique, graph colouring, maximum independent set, minimum vertex clique covering, minimum dominating set, as well as the longest simple cycle problem. Suboptimal solutions and intervals for optimal objective values are estimated using scalable heuristics. GraphCombEx has previously or currently been tested in scenarios of exploring synthetic graph models, as well as real-world networks ranging from social network samples, biological networks, to very large networks from the SNAP network data repository. The tool has already been successfully used to support a number of recent studies and is particularly beneficial in exploring the combinatorial properties of previously unseen network data, before applying more sophisticated custom optimisation algorithms.

Original languageEnglish
JournalSoft Computing
Volume23
Pages (from-to)5715-5724
Number of pages10
ISSN1432-7643
DOIs
Publication statusPublished - 2019

Keywords

  • Combinatorial optimisation problems
  • Complex networks
  • Graph combinatorial explorer
  • GraphCombEx
  • Large sparse graphs
  • Research software

Fingerprint Dive into the research topics of 'GraphCombEx: A Software Tool for Exploration of Combinatorial Optimisation Properties of Large Graphs'. Together they form a unique fingerprint.

  • Cite this