| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 6875897 | Theoretical Computer Science | 2017 | 27 Pages |
Abstract
While for 2ECS and 2VCS one can obtain an approximation ratio smaller than 2 by combining previously known results, providing good approximations for the 2-edge and the 2-vertex-components case seems more challenging. Here, we present linear-time approximation algorithms that achieve the following approximation guarantees:
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Loukas Georgiadis, Giuseppe F. Italiano, Aikaterini Karanasiou, Charis Papadopoulos, Nikos Parotsidis,