 |
|
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, EndNote, RefWorks, Mendeley |
