3 citations · 5 across the 9 of their papers we have counts for
13 papers
Greedy Coloring and Simple Exponential Strengthenings of Brooks-Type Theorems
Alex Crane, Carl Feghali, Felicia Lucke +2
Brooks' Theorem is a foundational result in graph coloring: if a graph is connected, not a clique, and has maximum degree , then it admits a proper -coloring. In this p…
An Evaluation of Vertex Elimination Strategies for Algorithmic Differentiation
Alex Crane, Pål Grønås Drange, Eli Friedman +6
The algorithmic differentiation (AD) of mathematical functions can be interpreted as a sequence of vertex eliminations in an underlying directed acyclic graph. The problem of deter…
Aggregating maximal cliques in real-world graphs
Noga Alon, Sabyasachi Basu, Shweta Jain +3
Maximal clique enumeration is a fundamental graph mining task, but its utility is often limited by computational intractability and highly redundant output. To address these challe…
Structural Optimal Jacobian Accumulation and Minimum Edge Count are NP-Complete Under Vertex Elimination
Matthias Bentert, Alex Crane, Pål Grønås Drange +2
We study graph-theoretic formulations of two fundamental problems in algorithmic differentiation. The first (Structural Optimal Jacobian Accumulation) is that of computing a Jacobi…
Equalizing Closeness Centralities via Edge Additions
Alex Crane, Sorelle A. Friedler, Mihir Patel +3
Graph modification problems with the goal of optimizing some measure of a given node's network position have a rich history in the algorithms literature. Less commonly explored are…
Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges
Alex Crane, Thomas Stanley, Blair D. Sullivan +1
We consider a framework for clustering edge-colored hypergraphs, where the goal is to cluster (equivalently, to color) objects based on the primary type of multiway interactions th…
A Space-Efficient Algebraic Approach to Robotic Motion Planning
Matthias Bentert, Daniel Coimbra Salomao, Alex Crane +3
We consider efficient route planning for robots in applications such as infrastructure inspection and automated surgical imaging. These tasks can be modeled via the combinatorial p…
Fast algorithms to improve fair information access in networks
Dennis Robert Windham, Caroline J. Wendt, Alex Crane +5
We consider the problem of selecting seed nodes in a network to maximize the minimum probability of activation under an independent cascade beginning at these seeds. The motiva…
Optimizing Probabilistic Propagation in Graphs by Adding Edges
Aditya Bhaskara, Alex Crane, Shweta Jain +3
Probabilistic graphs are an abstraction that allow us to study randomized propagation in graphs. In a probabilistic graph, each edge is "active" with a certain probability, indepen…
Leveraging Fixed-Parameter Tractability for Robot Inspection Planning
Yosuke Mizutani, Daniel Coimbra Salomao, Alex Crane +5
Autonomous robotic inspection, where a robot moves through its environment and inspects points of interest, has applications in industrial settings, structural health monitoring, a…
Correlation Clustering with Vertex Splitting
Matthias Bentert, Alex Crane, Pål Grønås Drange +2
We explore Cluster Editing and its generalization Correlation Clustering with a new operation called permissive vertex splitting which addresses finding overlapping clusters in the…
Cluster Editing with Vertex Splitting
Faisal N. Abu-Khzam, Emmanuel Arrighi, Matthias Bentert +7
Cluster Editing, also known as Correlation Clustering, is a well-studied graph modification problem. In this problem, one is given a graph and the task is to perform up to edge…
Hyperbolicity, degeneracy, and expansion of random intersection graphs
Matthew Farrell, Timothy Goodrich, Nathan Lemons +3
We establish the conditions under which several algorithmically exploitable structural features hold for random intersection graphs, a natural model for many real-world networks wh…