27 citations · 100 across the 31 of their papers we have counts for
42 papers
A combinatorial framework for clustering graph states: Algorithms and hardness for rank-integrity
Romain Bourneuf, Nathan Claudet, Sang Yoon Kim +3
We introduce a new notion of distance between two graph states and on the same set of qubits. This distance is the minimum number of ancilla qubits in a gr…
Edge interventions can mitigate demographic and prestige disparities in the Computer Science coauthorship network
Kate Barnes, Mia Ellis-Einhorn, Carolina Chávez-Ruelas +5
Social factors such as demographic traits and institutional prestige structure the creation and dissemination of ideas in academic publishing. One place these effects can be observ…
Preprocessing to Reduce the Search Space for Odd Cycle Transversal
Bart M. P. Jansen, Yosuke Mizutani, Blair D. Sullivan +1
The NP-hard Odd Cycle Transversal problem asks for a minimum vertex set whose removal from an undirected input graph breaks all odd cycles, and thereby yields a bipartite graph…
Open Problems in (Hyper)Graph Decomposition
Deepak Ajwani, Rob H. Bisseling, Katrin Casel +26
Large networks are useful in a wide range of applications. Sometimes problem instances are composed of billions of entities. Decomposing and analyzing these structures helps us gai…
Overlapping and Robust Edge-Colored Clustering in Hypergraphs
Alex Crane, Brian Lavallee, Blair D. Sullivan +1
A recent trend in data mining has explored (hyper)graph clustering algorithms for data with categorical relationship types. Such algorithms have applications in the analysis of soc…
Reducing Access Disparities in Networks using Edge Augmentation
Ashkan Bashardoust, Sorelle A. Friedler, Carlos E. Scheidegger +2
In social networks, a node's position is a form of \it{social capital}. Better-positioned members not only benefit from (faster) access to diverse information, but innately have mo…
Improved Parameterized Complexity of Happy Set Problems
Yosuke Mizutani, Blair D. Sullivan
We present fixed-parameter tractable (FPT) algorithms for two problems, Maximum Happy Set (MaxHS) and Maximum Edge Happy Set (MaxEHS)--also known as Densest k-Subgraph. Given a gra…
Faster Decomposition of Weighted Graphs into Cliques using Fisher's Inequality
Shweta Jain, Yosuke Mizutani, Blair Sullivan
Mining groups of genes that consistently co-express is an important problem in biomedical research, where it is critical for applications such as drug-repositioning and designing n…
Parameterized Complexity of Gerrymandering
Andrew Fraser, Brian Lavallee, Blair D. Sullivan
In a representative democracy, the electoral process involves partitioning geographical space into districts which each elect a single representative. These representatives craft a…
Minimizing Congestion for Balanced Dominators
Yosuke Mizutani, Annie Staker, Blair D. Sullivan
A primary challenge in metagenomics is reconstructing individual microbial genomes from the mixture of short fragments created by sequencing. Recent work leverages the sparsity of…
Hardness of the Generalized Coloring Numbers
Michael Breen-McKay, Brian Lavallee, Blair D. Sullivan
The generalized coloring numbers of Kierstead and Yang (Order 2003) offer an algorithmically-useful characterization of graph classes with bounded expansion. In this work, we consi…
Parameterized algorithms for identifying gene co-expression modules via weighted clique decomposition
Madison Cooley, Casey S. Greene, Davis Issac +2
We present a new combinatorial model for identifying regulatory modules in gene co-expression data using a decomposition into weighted cliques. To capture complex interaction effec…
Information access representations and social capital in networks
Ashkan Bashardoust, Hannah C. Beilinson, Sorelle A. Friedler +6
Social network position confers power and social capital. In the setting of online social networks that have massive reach, creating mathematical representations of social capital…
A color-avoiding approach to subgraph counting in bounded expansion classes
Felix Reidl, Blair D. Sullivan
We present an algorithm to count the number of occurrences of a pattern graph as an induced subgraph in a host graph . If belongs to a bounded expansion class, the algor…
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…
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…
Subgraph centrality and walk-regularity
Eric Horton, Kyle Kloster, Blair D. Sullivan
Matrix-based centrality measures have enjoyed significant popularity in network analysis, in no small part due to our ability to rigorously analyze their behavior as parameters var…
Polynomial Treedepth Bounds in Linear Colorings
Jeremy Kun, Michael P. O'Brien, Marcin Pilipczuk +1
Low-treedepth colorings are an important tool for algorithms that exploit structure in classes of bounded expansion; they guarantee subgraphs that use few colors have bounded treed…
An Experimental Evaluation of a Bounded Expansion Algorithmic Pipeline
Michael P. O'Brien, Blair D. Sullivan
Previous work has suggested that the structural restrictions of graphs from classes of bounded expansion--locally dense pockets in a globally sparse graph--naturally coincide with…
Walk entropy and walk-regularity
Kyle Kloster, Daniel Král', Blair D. Sullivan
A graph is said to be walk-regular if, for each , every vertex is contained in the same number of closed walks of length . We construct a -vertex graph …