5 papers
A Polymatroidal Perspective on Random Contraction
Karthekeyan Chandrasekaran, Chandra Chekuri, Weihao Zhu
Karger's elegant random contraction algorithm for finding a global mincut in a graph has been highly influential. More recent work has obtained several different (nonuniform) rando…
Multiobjective Hypergraph Min-Cut in Quasi-Polynomial Time
Karthekeyan Chandrasekaran, Chandra Chekuri, Weihao Zhu
We study the multiobjective hypergraph min-cut problem: Given a hypergraph and cost functions , the goal is to find a no…
Hedgegraph Polymatroids
Karthekeyan Chandrasekaran, Chandra Chekuri, Weihang Wang +1
Graphs and hypergraphs combine expressive modeling power with algorithmic efficiency for a wide range of applications. Hedgegraphs generalize hypergraphs further by grouping hypere…
Online Disjoint Spanning Trees and Polymatroid Bases
Karthekeyan Chandrasekaran, Chandra Chekuri, Weihao Zhu
Finding the maximum number of disjoint spanning trees in a given graph is a well-studied problem with several applications and connections. The Tutte-Nash-Williams theorem provides…
From Directed Steiner Tree to Directed Polymatroid Steiner Tree in Planar Graphs
Chandra Chekuri, Rhea Jain, Shubhang Kulkarni +2
In the Directed Steiner Tree (DST) problem the input is a directed edge-weighted graph , a root vertex and a set of terminals. The goal is to find…