Paper Info
Title
GraphCombEx: A Software Tool for Exploration of Combinatorial Optimisation Properties of Large Graphs.
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.
Year
DOI
Venue
2018
10.1007/s00500-018-3230-x
Soft Computing
Keywords
Field
DocType
GraphCombEx, Graph combinatorial explorer, Complex networks, Large sparse graphs, Combinatorial optimisation problems, Research software
Mathematical optimization,Clique,Vertex (geometry),Computer science,Biological network,Theoretical computer science,Heuristics,Independent set,Complex network,Scalability,Computation
Journal
Volume
Issue
ISSN
abs/1801.09229
14
1432-7643
Citations 
PageRank 
References 
1
0.36
23
Authors
2
Name
Order
Citations
PageRank
David Chalupa1246.84
K. A. Hawick229366.26