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

DOI10.1016/J.IPL.2004.01.011zbMATH Open1178.68377OpenAlexW2084112594MaRDI QIDQ2390219FDOQ2390219

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

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

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)

Cites Work

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

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
• The connected vertex cover problem in \(k\)-regular graphs
• Polynomial Time Approximation Scheme for Connected Vertex Cover in Unit Disk Graph
• Enumerate and Measure: Improving Parameter Budget Management
• 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)