On the parameterized complexity of the edge monitoring problem

DOI10.1016/J.IPL.2017.01.008zbMATH Open1404.68080OpenAlexW2583078788MaRDI QIDQ509893FDOQ509893

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

Recommendations

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

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)

Cites Work

• Fundamentals of parameterized complexity
• Unit disk graphs
• The extremal function for complete minors
• Parametrized complexity theory.
• Title not available (Why is that?)
• Treewidth. Computations and approximations
• Contraction obstructions for treewidth
• Linearity of grid minors in treewidth with applications through bidimensionality
• Mathematical Foundations of Computer Science 2004
• Subexponential parameterized algorithms on graphs of bounded-genus and \(H\)-minor-free 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)