Constant factor approximation for tracking paths and fault tolerant feedback vertex set
type: Item
instance of: scholarly article
title: Constant factor approximation for tracking paths and fault tolerant feedback vertex set
DOI: 10.1007/978-3-030-92702-8_2
author: Václav Blažej
author: Pratibha Choudhary
author: Dušan Knop
author: Jan Matyáš Křišt'an
author: Ondřej Suchý
author: T. Valla
published in: Approximation and Online Algorithms
publication date: 2022-10-19T00:00:00Z
full work available at URL: https://arxiv.org/abs/2108.01430
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 68W27
zbMATH DE Number: 7603882
MaRDI profile type: MaRDI publication profile
OpenAlex ID: W3191204702
cites work: Polylogarithmic Approximation Algorithms for Weighted-ℱ-deletion Problems
cites work: A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
cites work: A polynomial sized kernel for tracking paths problem
cites work: Fixed-parameter tractable algorithms for tracking shortest paths
cites work: Tracking paths
cites work: Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
cites work: Tracking routes in communication networks
cites work: Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width
cites work: Rumor spreading in social networks
cites work: Polynomial Time Algorithms for Tracking Path Problems
cites work: A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
cites work: Approximation algorithms for \(k\)-hurdle problems
cites work: Graph Theory
cites work: Q5875621
cites work: Approximating the k-multicut problem
cites work: How to catch marathon cheaters: new approximation algorithms for tracking paths
cites work: The ellipsoid method and its consequences in combinatorial optimization
cites work: Geometric algorithms and combinatorial optimization
cites work: Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs
cites work: Reducibility among Combinatorial Problems
cites work: The disjoint paths problem in quadratic time
cites work: Detecting Feedback Vertex Sets of Size k in O*(2.7k) Time
cites work: Q4967205
description: scientific article; zbMATH DE number 7603882