Vertex Sparsification for Edge Connectivity

Graph compression or sparsification is a basic information-theoretic and computational question. A major open problem in this research area is whether $(1+ε)$-approximate cut-preserving vertex sparsifiers with size close to the number of terminals exist. As a step towards this goal, we study a thres...

Full description

Bibliographic Details

Main Authors:	Chalermsook, Parinya, Das, Syamantak, Laekhanukit, Bundit, Kook, Yunbum, Liu, Yang P., Peng, Richard, Sellke, Mark, Vaz, Daniel
Format:	Article
Published:	2020
Subjects:	Data Structures and Algorithms
Online Access:	https://arxiv.org/abs/2007.07862 http://arxiv.org/abs/2007.07862
Tags:	Add Tag No Tags, Be the first to tag this record!