Optimization Online


Detecting Almost Symmetries of Graphs

Ben Knueven (bknueven***at***vols.utk.edu)
Jim Ostrowski (jostrows***at***utk.edu)
Sebastian Pokutta (sebastian.pokutta***at***isye.gatech.edu)

Abstract: We present a branch-and-bound framework to solve the following problem: Given a graph G and an integer k, find a subgraph of G formed by removing no more than k edges that contains the most symmetry. We call symmetries on such a subgraph ``almost symmetries'' of G. We implement our branch-and-bound framework in PEBBL to allow for parallel enumeration and demonstrate good scaling up to 16 cores. We show that the presented branching strategy is much better than a random branching strategy on the tested graphs.

Keywords: graph automorphism, branch-and-bound

Category 1: Combinatorial Optimization (Other )

Citation: University of Tennessee, September 2015

Download: [PDF]

Entry Submitted: 09/22/2015
Entry Accepted: 09/23/2015
Entry Last Modified: 08/04/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society