Structural parameterizations of Tracking Paths problem

DOI10.1016/J.TCS.2022.09.009OpenAlexW3081273719MaRDI QIDQ2089072FDOQ2089072

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)

Cites Work

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

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)