research
∙
08/30/2023
Independent set in k-Claw-Free Graphs: Conditional χ-boundedness and the Power of LP/SDP Relaxations
This paper studies k-claw-free graphs, exploring the connection between ...
share
research
∙
07/05/2023
Sorting Pattern-Avoiding Permutations via 0-1 Matrices Forbidding Product Patterns
We consider the problem of comparison-sorting an n-permutation S that av...
research
∙
07/03/2023
Polynomial-time Approximation of Independent Set Parameterized by Treewidth
We prove the following result about approximating the maximum independen...
research
∙
05/12/2023
Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces
We consider the well-studied Robust (k, z)-Clustering problem, which gen...
research
∙
04/06/2023
Parameterized Approximation Schemes for Clustering with General Norm Objectives
This paper considers the well-studied algorithmic regime of designing a ...
research
∙
11/08/2022
Improved Pattern-Avoidance Bounds for Greedy BSTs via Matrix Decomposition
Greedy BST (or simply Greedy) is an online self-adjusting binary search ...
research
∙
05/30/2022
Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver
In the k-edge-connected spanning subgraph (kECSS) problem, our goal is t...
research
∙
11/11/2021
Approximating Sparsest Cut in Low-Treewidth Graphs via Combinatorial Diameter
The fundamental sparsest cut problem takes as input a graph G together w...
research
∙
10/27/2020
On Minimum Generalized Manhattan Connections
We consider minimum-cardinality Manhattan connected sets with arbitrary ...
research
∙
07/15/2020
Coloring and Maximum Weight Independent Set of Rectangles
In 1960, Asplund and Grünbaum proved that every intersection graph of ax...
research
∙
07/15/2020
Vertex Sparsification for Edge Connectivity
Graph compression or sparsification is a basic information-theoretic and...
research
∙
01/01/2020
Multi-transversals for Triangles and the Tuza's Conjecture
In this paper, we study a primal and dual relationship about triangles: ...
research
∙
12/05/2019
Pinning Down the Strong Wilber 1 Bound for Binary Search Trees
The famous dynamic optimality conjecture of Sleator and Tarjan from 1985...
research
∙
10/23/2019
Mimicking Networks Parameterized by Connectivity
Given a graph G=(V,E), capacities w(e) on edges, and a subset of termina...
research
∙
09/05/2018
Multi-finger binary search trees
We study multi-finger binary search trees (BSTs), a far-reaching extensi...
research
∙
04/10/2018
A Tight Extremal Bound on the Lovász Cactus Number in Planar Graphs
A cactus graph is a graph in which any two cycles are edge-disjoint. We ...
research
∙
02/28/2018
Survivable Network Design for Group Connectivity in Low-Treewidth Graphs
In the Group Steiner Tree problem (GST), we are given a (vertex or edge)...
research
∙
08/14/2017
From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More
We consider questions that arise from the intersection between the areas...
research
∙
08/11/2017
