Depth-first search and the vertex cover problem
From MaRDI portal
Publication:1171390
DOI10.1016/0020-0190(82)90022-9zbMath0498.68041OpenAlexW2065161629MaRDI QIDQ1171390
Publication date: 1982
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(82)90022-9
approximate solutiongraph algorithmsapproximation algorithmscombinatorial algorithmsdepth-first search spanning tree
Trees (05C05) Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10)
Related Items (33)
Equivalent approximation algorithms for node cover ⋮ An Articulation Point-Based Approximation Algorithm for Minimum Vertex Cover Problem ⋮ Safe Approximation and Its Relation to Kernelization ⋮ On approximating (connected) 2-edge dominating set by a tree ⋮ On approximation algorithms for the minimum satisfiability problem ⋮ Maximum weight independent set in trees ⋮ A 2-approximation NC algorithm for connected vertex cover and tree cover ⋮ Neighborhood covering and independence on \(P_4\)-tidy graphs and tree-cographs ⋮ Approximation for vertex cover in \(\beta\)-conflict graphs ⋮ \(p\)-edge/vertex-connected vertex cover: parameterized and approximation algorithms ⋮ The connected vertex cover problem in \(k\)-regular graphs ⋮ Complexity and Approximation Results for the Connected Vertex Cover Problem ⋮ Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP ⋮ Fully dynamic maintenance of vertex cover ⋮ Unnamed Item ⋮ An efficient heuristic algorithm for solving connected vertex cover problem ⋮ Connected Vertex Covers in Dense Graphs ⋮ Approximate Turing Kernelization for Problems Parameterized by Treewidth ⋮ Complexity and algorithms for the connected vertex cover problem in 4-regular graphs ⋮ A primal-dual method for approximating tree cover with two weights ⋮ On the approximate compressibility of connected vertex cover ⋮ On Approximating (Connected) 2-Edge Dominating Set by a Tree ⋮ Connected vertex covers in dense graphs ⋮ Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs ⋮ The simultaneous strong metric dimension of graph families ⋮ Vertex and edge covers with clustering properties: Complexity and algorithms ⋮ On approximation problems related to the independent set and vertex cover problems ⋮ Extension and its price for the connected vertex cover problem ⋮ PTAS for connected vertex cover in unit disk graphs ⋮ Polynomial Time Approximation Scheme for Connected Vertex Cover in Unit Disk Graph ⋮ A Primal-Dual Method for Approximating Tree Cover with Two Weights ⋮ On approximability of the independent/connected edge dominating set problems ⋮ Multi-rooted greedy approximation of directed Steiner trees with applications
Cites Work
This page was built for publication: Depth-first search and the vertex cover problem
