A 2-approximation NC algorithm for connected vertex cover and tree cover

DOI10.1016/J.IPL.2004.01.011MaRDI QIDQ2390219zbMATH OpenOpenAlexFDO

Authors Toshihiro Fujito, Takashi Doi

Publication date 21 July 2009

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2004.01.011

zbMATH Keywords

approximation algorithmsparallel algorithmsconnected vertex covertree cover

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• Approximating unweighted connectivity problems in parallel
• Approximating biconnectivity in parallel
• Solving NP-hard problems in 'almost trees': vertex cover
• Complexity and Approximation Results for the Connected Vertex Cover Problem
• scientific article; zbMATH DE number 8779

Cites work

• scientific article; zbMATH DE number 1670541 (Why is no real title available?)
• scientific article; zbMATH DE number 3869066 (Why is no real title available?)
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 1256748 (Why is no real title available?)
• scientific article; zbMATH DE number 1263280 (Why is no real title available?)
• scientific article; zbMATH DE number 2080196 (Why is no real title available?)
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast and efficient NC algorithm for maximal matching
• A fast and simple randomized parallel algorithm for maximal matching
• A random NC algorithm for depth first search
• An Efficient Parallel Biconnectivity Algorithm
• An improved parallel algorithm that computes the BFS numbering of a directed graph
• An optimal parallel algorithm for maximal matching
• Approximating the tree and tour covers of a graph
• Approximation algorithms for NP-hard problems.
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Depth-first search and the vertex cover problem
• Matching is as easy as matrix inversion
• Paradigms for Fast Parallel Approximability
• Ramsey numbers and an approximation algorithm for the vertex cover problem
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• The intersection graphs of subtrees in trees are exactly the chordal graphs

Cited in

(10)

• Complexity and algorithms for the connected vertex cover problem in 4-regular graphs
• Connected Vertex Covers in Dense Graphs
• Connected vertex covers in dense graphs
• PTAS for connected vertex cover in unit disk graphs
• Enumerate and measure: improving parameter budget management
• The connected vertex cover problem in \(k\)-regular graphs
• Polynomial Time Approximation Scheme for Connected Vertex Cover in Unit Disk Graph
• Two fixed-parameter algorithms for vertex covering by paths on trees
• Parameterized measure \& conquer for problems with no small kernels
• An efficient heuristic algorithm for solving connected vertex cover problem

This page was built for publication: A 2-approximation NC algorithm for connected vertex cover and tree cover

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2390219)