Davis Issac

most citedOptimal Padded Decomposition For Bounded Treewidth Graphs

2 citations · 2 across the 3 of their papers we have counts for

collaborators

3 papers

cs.DS2024★ 2 cited

Optimal Padded Decomposition For Bounded Treewidth Graphs

Arnold Filtser, Tobias Friedrich, Davis Issac +4

A $(β, δ, Δ)$ -padded decomposition of an edge-weighted graph $G = (V, E, w)$ is a stochastic decomposition into clusters of diameter at most $Δ$ such that for every vertex $v \in V$ , th…

cs.DS2022

Approximate Max-Flow Min-Multicut Theorem for Graphs of Bounded Treewidth

Tobias Friedrich, Davis Issac, Nikhil Kumar +2

We prove an approximate max-multiflow min-multicut theorem for bounded treewidth graphs. In particular, we show the following: Given a treewidth- $r$ graph, there exists a (fraction…

cs.DS2022

Efficient Constructions for the Győri-Lovász Theorem on Almost Chordal Graphs

Katrin Casel, Tobias Friedrich, Davis Issac +2

In the 1970s, Győri and Lovász showed that for a $k$ -connected $n$ -vertex graph, a given set of terminal vertices $t_{1}, \dots, t_{k}$ and natural numbers $n_{1}, \dots, n_{k}$ satisfying…