Structural parameterizations of Tracking Paths problem

DOI10.1016/J.TCS.2022.09.009MaRDI QIDQ2089072zbMATH OpenOpenAlexFDO

Authors Pratibha Choudhary, Venkatesh Raman

Publication date 6 October 2022

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2008.09806

zbMATH Keywords

undirected graphsvertex coversplit graphsstructural parameterizationedge clique covercluster vertex deletion setTracking Paths

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Fixed-parameter tractable algorithms for tracking set problems
• Fixed-parameter tractable algorithms for tracking shortest paths
• A polynomial sized kernel for tracking paths problem
• A polynomial sized kernel for tracking paths problem
• Improved kernels for tracking paths

Cites work

• A Practical Approach to Courcelle's Theorem
• A polynomial sized kernel for tracking paths problem
• Data reduction for graph coloring problems
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Fixed-parameter tractable algorithms for tracking set problems
• Fixed-parameter tractable algorithms for tracking shortest paths
• Fundamentals of parameterized complexity
• Parameterized algorithms
• Parametrized complexity theory.
• Polynomial Time Algorithms for Tracking Path Problems
• Structural parameterizations of undirected feedback vertex set: FPT algorithms and kernelization
• The disjoint paths problem in quadratic time
• Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
• Tracking paths
• Tracking routes in communication networks

Cited in

(4)

• Constant factor approximation for tracking paths and fault tolerant feedback vertex set
• The parameterized complexity of maximum betweenness centrality
• An object-oriented implementation of structural path-following
• Fixed-parameter tractable algorithms for tracking shortest paths

This page was built for publication: Structural parameterizations of Tracking Paths problem

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