On the parameterized complexity of the edge monitoring problem

DOI10.1016/j.ipl.2017.01.008zbMath1404.68080OpenAlexW2583078788MaRDI QIDQ509893

Julien Baste, Fairouz Beggas, Ignasi Sau, Hamamache Kheddouci

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 algorithmsparameterized complexityFPT algorithmbidimensionality theoryEdge Monitoring

Mathematics Subject Classification ID

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) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Complexity of edge monitoring on some graph classes ⋮ On the distance-edge-monitoring numbers of graphs ⋮ Monitoring the edges of a graph using distances

Cites Work

• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Linearity of grid minors in treewidth with applications through bidimensionality
• Unit disk graphs
• Treewidth. Computations and approximations
• The extremal function for complete minors
• Contraction obstructions for treewidth
• Parametrized complexity theory.
• Mathematical Foundations of Computer Science 2004

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