Complexity of edge monitoring on some graph classes
2022
In this paper, we study the complexity of the edge monitoring problem. A vertex monitors an edge if both endpoints together with form a triangle in the graph. Given a graph and a weight function on edges where is the number of monitors that needs the edge , the problem is to seek a minimum subset of monitors such that every edge in the graph is monitored by at least vertices in . Therefore, we study the edge monitoring problem on several graph classes such as complete graphs, block graphs, cographs, split graphs, interval graphs and planar graphs. We also generalize the problem by adding weights on vertices.
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
0
References
0
Citations
NaN
KQI