4 papers
Graph Profiling for Vertex Cover: Targeted Reductions in a Branch and Reduce Solver
Matthias F. Stallmann, Yang Ho, Timothy D. Goodrich
Akiba and Iwata [TCS, 2016] demonstrated that a branch and reduce (B&R) solver for the vertex cover problem can compete favorably with integer linear programming solvers (e.g., CPL…
Benchmarking treewidth as a practical component of tensor-network--based quantum simulation
Eugene F. Dumitrescu, Allison L. Fisher, Timothy D. Goodrich +3
Tensor networks are powerful factorization techniques which reduce resource requirements for numerically simulating principal quantum many-body systems and algorithms. The computat…
Structural Rounding: Approximation Algorithms for Graphs Near an Algorithmically Tractable Class
Erik D. Demaine, Timothy D. Goodrich, Kyle Kloster +5
We develop a new framework for generalizing approximation algorithms from the structural graph algorithm literature so that they apply to graphs somewhat close to that class (a sce…
An Updated Experimental Evaluation of Graph Bipartization Methods
Timothy D. Goodrich, Eric Horton, Blair D. Sullivan
We experimentally evaluate the practical state-of-the-art in graph bipartization (Odd Cycle Transversal), motivated by recent advances in near-term quantum computing hardware and t…