arXiv Open Access 2017

Linear-time approximation schemes for planar minimum three-edge connected and three-vertex connected spanning subgraphs

Baigong Zheng

Lihat Sumber

Abstrak

We present the first polynomial-time approximation schemes, i.e., (1 + ε)-approximation algorithm for any constant ε > 0, for the minimum three-edge connected spanning subgraph problem and the minimum three-vertex connected spanning subgraph problem in undirected planar graphs. Both the approximation schemes run in linear time.

Topik & Kata Kunci

cs.DS

Penulis (1)

Baigong Zheng

Format Sitasi

APA MLA BibTeX

Zheng, B. (2017). Linear-time approximation schemes for planar minimum three-edge connected and three-vertex connected spanning subgraphs. https://arxiv.org/abs/1701.08315

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2017
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓