58 citations · 151 across the 35 of their papers we have counts for
4 papers · 1 filter
Near-linear-time, Optimal Vertex Cut Sparsifiers in Directed Acyclic Graphs
Zhiyang He, Jason Li, Magnus Wahlström
Let be a graph and be (possibly overlapping) sets of terminals, . We are interested in computing a vertex sparsifier for terminal cuts in ,…
p-Edge/Vertex-Connected Vertex Cover: Parameterized and Approximation Algorithms
Carl Einarson, Gregory Gutin, Bart M. P. Jansen +2
We introduce and study two natural generalizations of the Connected VertexCover (VC) problem: the -Edge-Connected and -Vertex-Connected VC problem (where is a fixe…
Component Order Connectivity in Directed Graphs
J. Bang-Jensen, E. Eiben, G. Gutin +2
A directed graph is semicomplete if for every pair of vertices of there is at least one arc between and \viol{Thus, a tournament is a semicomplete digraph.}…
Flow-augmentation II: Undirected graphs
Eun Jung Kim, Stefan Kratsch, Marcin Pilipczuk +1
We present an undirected version of the recently introduced flow-augmentation technique: Given an undirected multigraph with distinguished vertices and an intege…