5 papers
Approximating Vertex Cover using Structural Rounding
Brian Lavallee, Hayley Russell, Blair D. Sullivan +1
In this work, we provide the first practical evaluation of the structural rounding framework for approximation algorithms. Structural rounding works by first editing to a well-stru…
Faster Biclique Mining in Near-Bipartite Graphs
Blair D. Sullivan, Andrew van der Poel, Trey Woodlief
Identifying dense bipartite subgraphs is a common graph data mining task. Many applications focus on the enumeration of all maximal bicliques (MBs), though sometimes the stricter v…
Mining Maximal Induced Bicliques using Odd Cycle Transversals
Kyle Kloster, Blair D. Sullivan, Andrew van der Poel
Many common graph data mining tasks take the form of identifying dense subgraphs (e.g. clustering, clique-finding, etc). In biological applications, the natural model for these den…
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…
A practical fpt algorithm for Flow Decomposition and transcript assembly
Kyle Kloster, Philipp Kuinke, Michael P. O'Brien +4
The Flow Decomposition problem, which asks for the smallest set of weighted paths that "covers" a flow on a DAG, has recently been used as an important computational step in transc…