
Hardness of Token Swapping on Trees
Given a graph where every vertex has exactly one labeled token, how can ...
read it

Simple Combinatorial Algorithms for the Minimum Dominating Set Problem in Bounded Arboricity Graphs
We revisit the minimum dominating set problem on graphs with arboricity ...
read it

Tight Conditional Lower Bounds for Approximating Diameter in Directed Graphs
Among the most fundamental graph parameters is the Diameter, the largest...
read it

New Techniques and FineGrained Hardness for Dynamic NearAdditive Spanners
Maintaining and updating shortest paths information in a graph is a fund...
read it

Algorithms and Lower Bounds for the WorkerTask Assignment Problem
We study the problem of assigning workers to tasks where each task has d...
read it

Lower Bounds for Dynamic Distributed Task Allocation
We study the problem of distributed task allocation in multiagent syste...
read it

New Algorithms and Hardness for Incremental SingleSource Shortest Paths in Directed Graphs
In the dynamic SingleSource Shortest Paths (SSSP) problem, we are given...
read it

Improved Dynamic Graph Coloring
This paper studies the fundamental problem of graph coloring in fully dy...
read it

Approximation Algorithms for MinDistance Problems
We study fundamental graph parameters such as the Diameter and Radius in...
read it

Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems
Some of the most fundamental and wellstudied graph parameters are the D...
read it

Algorithms and Hardness for Diameter in Dynamic Graphs
The diameter, radius and eccentricities are natural graph parameters. Wh...
read it

Fully Dynamic MIS in Uniformly Sparse Graphs
We consider the problem of maintaining a maximal independent set (MIS) i...
read it

Towards Tight Approximation Bounds for Graph Diameter and Eccentricities
Among the most important graph parameters is the Diameter, the largest d...
read it

Finding Cliques in Social Networks: A New DistributionFree Model
We propose a new distributionfree model of social networks. Our definit...
read it
Nicole Wein
is this you? claim profile