K. Chandrasekaran

activity

20092026

most citedThe Cutting Plane Method is Polynomial for Perfect Matchings

7 citations · 29 across the 31 of their papers we have counts for

collaborators

Showing 2020Show all

4 papers · 1 filter

cs.DS2020

Fixed Parameter Approximation Scheme for Min-max $k$ -cut

Karthekeyan Chandrasekaran, Weihang Wang

We consider the graph $k$ -partitioning problem under the min-max objective, termed as Minmax $k$ -cut. The input here is a graph $G = (V, E)$ with non-negative edge weights $w:E\righta…

cs.DS2020

Faster connectivity in low-rank hypergraphs via expander decomposition

Calvin Beideman, Karthekeyan Chandrasekaran, Sagnik Mukhopadhyay +1

We design an algorithm for computing connectivity in hypergraphs which runs in time $O^_{r} (p + min {λ^{\frac{r - 3}{r - 1}} n^{2}, n^{r} / λ^{r / (r - 1)}})$ (the $O^_{r} (\cdot)$ hides th…

cs.DS2020

Hypergraph $k$ -cut for fixed $k$ in deterministic polynomial time

Karthekeyan Chandrasekaran, Chandra Chekuri

We consider the Hypergraph- $k$ -cut problem. The input consists of a hypergraph $G = (V, E)$ with non-negative hyperedge-costs $c : E \to R_{+}$ and a positive integer $k$ . The obj…

cs.DS2020

Multicritera Cuts and Size-Constrained $k$ -cuts in Hypergraphs

Calvin Beideman, Karthekeyan Chandrasekaran, Chao Xu

We address counting and optimization variants of multicriteria global min-cut and size-constrained min- $k$ -cut in hypergraphs. 1. For an $r$ -rank $n$ -vertex hypergraph endowed with…

Fixed Parameter Approximation Scheme for Min-max k-cut

Faster connectivity in low-rank hypergraphs via expander decomposition

Hypergraph k-cut for fixed k in deterministic polynomial time

Multicritera Cuts and Size-Constrained k-cuts in Hypergraphs

Fixed Parameter Approximation Scheme for Min-max $k$ -cut

Hypergraph $k$ -cut for fixed $k$ in deterministic polynomial time

Multicritera Cuts and Size-Constrained $k$ -cuts in Hypergraphs