Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Subgraph Problem
 
research article

A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Subgraph Problem

Hunkenschroeder, Christoph  
•
Vempala, Santosh
•
Vetta, Adrian
October 1, 2019
Acm Transactions On Algorithms

We present a factors 4/3 approximation algorithm for the problem of finding a minimum 2-edge connected spanning subgraph of a given undirected multigraph. The algorithm is based upon a reduction to a restricted class of graphs. In these graphs, the approximation algorithm constructs a 2-edge connected spanning subgraph by modifying the smallest 2-edge cover.

  • Details
  • Metrics
Type
research article
DOI
10.1145/3341599
Web of Science ID

WOS:000496745500011

Author(s)
Hunkenschroeder, Christoph  
Vempala, Santosh
Vetta, Adrian
Date Issued

2019-10-01

Published in
Acm Transactions On Algorithms
Volume

15

Issue

4

Start page

55

Subjects

Computer Science, Theory & Methods

•

Mathematics, Applied

•

Computer Science

•

Mathematics

•

approximation algorithms

•

graph connectivity

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DISOPT  
Available on Infoscience
November 29, 2019
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/163464
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés