Complexity of edge monitoring on some graph classes

DOI10.1016/J.DAM.2022.06.014zbMath1497.05232arXiv1710.02013OpenAlexW2763756726MaRDI QIDQ2172388

Guillaume Bagan, Fairouz Beggas, Hamamache Kheddouci, Mohammed Haddad

Publication date: 15 September 2022

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

complexityalgorithmsapproximationdominationedge monitoringparameterizedweighted edge monitoring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Structural characterization of families of graphs (05C75) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Signed and weighted graphs (05C22)

Uses Software

• Algorithm 447

Cites Work

• Unnamed Item
• On the parameterized complexity of the edge monitoring problem
• Edge monitoring problem on interval graphs
• Approximation hardness of dominating set problems in bounded degree graphs
• \(k\)-tuple domination in graphs
• Unit disk graphs
• Treewidth. Computations and approximations
• Unit disk graph recognition is NP-hard
• Diameter and treewidth in minor-closed graph families
• A simple linear time algorithm for cograph recognition
• Parametrized complexity theory.
• Universality considerations in VLSI circuits
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• Approximation algorithms for NP-complete problems on planar graphs

This page was built for publication: Complexity of edge monitoring on some graph classes