Polynomial time algorithms for tracking path problems

DOI10.1007/S00453-022-00931-1MaRDI QIDQ2144269zbMATH OpenOpenAlexFDO

Authors Pratibha Choudhary

Publication date 1 June 2022

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/s00453-022-00931-1

zbMATH Keywords

approximationbounded degree graphschordal graphsgraphspathstournamentstracking paths

Mathematics Subject Classification ID

Graph theory (05Cxx) Algorithms in computer science (68Wxx)

Recommendations

• Polynomial Time Algorithms for Tracking Path Problems
• A polynomial sized kernel for tracking paths problem
• A polynomial sized kernel for tracking paths problem
• Tracking paths
• Tracking paths

Cites work

• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• A polynomial sized kernel for tracking paths problem
• A quick method for finding shortest pairs of disjoint paths
• Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs
• Disjoint paths in tournaments
• Finding k Disjoint Paths in a Directed Planar Graph
• Fixed-parameter tractable algorithms for tracking set problems
• Fixed-parameter tractable algorithms for tracking shortest paths
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 219267 (Why is no real title available?)
• scientific article; zbMATH DE number 4121482 (Why is no real title available?)
• scientific article; zbMATH DE number 4184603 (Why is no real title available?)
• scientific article; zbMATH DE number 7650287 (Why is no real title available?)
• Introduction to algorithms
• Polynomial Time Algorithms for Tracking Path Problems
• Separating codes and traffic monitoring
• Some simplified NP-complete graph problems
• The directed subgraph homeomorphism problem
• The disjoint paths problem in quadratic time
• The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments
• The Voting Problem
• Tournament games and Condorcet voting
• Tracking paths
• Tracking routes in communication networks

Cited in

(6)

• Polynomial kernels for tracking shortest paths
• Fixed-parameter tractable algorithms for tracking shortest paths
• scientific article; zbMATH DE number 3934720 (Why is no real title available?)
• The complexity of the tabulation of trajectory problems
• Polynomial Time Algorithms for Tracking Path Problems
• Distance-based (and path-based) covering problems for graphs of given cyclomatic number

This page was built for publication: Polynomial time algorithms for tracking path problems

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