Use your computer fearlessly.

Mission Services Articles Research

Symmetric graph algorithms

Authors: Brent Kirkpatrick

Journal: The Intrepid Publication Series (TIPS)

Year: 2021

Abstract: Every graph algorithm can be revised to consider symmetries. Whether considering the symmetries improves the running time depends on the algorithm and the problem instance. Here, we consider some classic graph algorithms: max clique, independent set, traveling sales person, max cut, and graph coloring. All of these algorithms are classic exponential-time algorithms for NP-hard problems. In the case where a graph with symmetries is presented to the algorithm, we can sometimes dramatically improve the running time.

Download: pdf

Bibliography: BibTeX,

What Is New? | Contact | Tips

© 2015-2021 Intrepid Net Computing. All rights reserved.