On the parameterized complexity of the edge monitoring problem

DOI10.1016/J.IPL.2017.01.008MaRDI QIDQ509893zbMATH OpenOpenAlexFDO

Authors Julien Baste, Fairouz Beggas, H. Kheddouci, Ignasi Sau

Publication date 21 February 2017

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2017.01.008

zbMATH Keywords

graph algorithmsFPT algorithmparameterized complexitybidimensionality theoryEdge Monitoring

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Complexity of edge monitoring on some graph classes
• Edge monitoring problem on interval graphs
• Monitoring edge-geodetic sets: hardness and graph products

Cites work

• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Contraction obstructions for treewidth
• Fundamentals of parameterized complexity
• Linearity of grid minors in treewidth with applications through bidimensionality
• Mathematical Foundations of Computer Science 2004
• Parametrized complexity theory.
• Subexponential parameterized algorithms on graphs of bounded-genus and \(H\)-minor-free graphs
• The extremal function for complete minors
• Treewidth. Computations and approximations
• Unit disk graphs

Cited in

(5)

• Parameterized Complexity of Edge Interdiction Problems
• Perturbation results for distance-edge-monitoring numbers
• On the distance-edge-monitoring numbers of graphs
• Complexity of edge monitoring on some graph classes
• Edge monitoring problem on interval graphs

This page was built for publication: On the parameterized complexity of the edge monitoring problem

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