Path hitting in acyclic graphs
type: Item
instance of: scholarly article
title: Path hitting in acyclic graphs
zbMATH Open document ID: 1176.68244
author: Ojas Parekh
author: Danny Segev
published in: Algorithmica
publication date: 2009-05-13T00:00:00Z
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 90C05
Mathematics Subject Classification ID: 90C35
zbMATH DE Number: 5553561
zbMATH Keywords: approximation algorithms
zbMATH Keywords: linear programming
zbMATH Keywords: primal-dual
zbMATH Keywords: edge cover
zbMATH Keywords: edge dominating set
zbMATH Keywords: tree augmentation
zbMATH Keywords: tree multicut
MaRDI profile type: Publication
full work available at URL: s00453-007-9087-5
OpenAlex ID: W2056155690
cites work: Reductions to 1–matching polyhedra
cites work: A \(2\frac{1}{10}\)-approximation algorithm for a generalization of the weighted edge-dominating set problem
cites work: On the hardness of approximating Multicut and Sparsest-Cut
cites work: A Greedy Heuristic for the Set-Covering Problem
cites work: Q5675543
cites work: Q4780785
cites work: A threshold of ln n for approximating set cover
cites work: Approximation Algorithms for Several Graph Augmentation Problems
cites work: A 2-approximation algorithm for the minimum weight edge dominating set problem
cites work: Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
cites work: Primal-dual approximation algorithms for integral flow and multicut in trees
cites work: A General Approximation Technique for Constrained Forest Problems
cites work: A factor 2 approximation algorithm for the generalized Steiner network problem
cites work: Approximation algorithms for combinatorial problems
cites work: On the power of unique 2-prover 1-round games
cites work: Approximation Algorithms for Graph Augmentation
cites work: Partial multicuts in trees
cites work: On the ratio of optimal integral and fractional covers
cites work: A 1-matching blossom-type algorithm for edge covering problems
cites work: Q4828945
cites work: Q4871750
cites work: Q4782696
DOI: 10.1007/S00453-007-9087-5
Recommended article: Path Hitting in Acyclic Graphs
Recommended article: Q5749311
Recommended article: Q4393273
Recommended article: Q3477977
Recommended article: Path Problems in Structured Graphs
Recommended article: Q4280473
Recommended article: Shortest paths in almost acyclic graphs
Recommended article: Graph-Theoretic Concepts in Computer Science
Recommended article: Paths in graphs
Recommended article: Paths and cycles of hypergraphs
description: scientific article; zbMATH DE number 5553561