Back to Search
Start Over
Complexity of Edge Monitoring on Some Graph Classes
- Publication Year :
- 2017
- Publisher :
- arXiv, 2017.
-
Abstract
- In this paper, we study the complexity of the edge monitoring problem. A vertex $v$ monitors an edge $e$ if both extremities together with $v$ form a triangle in the graph. Given a graph $G=(V,E)$ and a weight function on edges $c$ where $c(e)$ is the number of monitors that needs the edge $e$, the problem is to seek a minimum subset of monitors $S$ such that every edge $e$ in the graph is monitored by at least $c(e)$ vertices in $S$. In this paper, 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.
- Subjects :
- FOS: Computer and information sciences
Discrete Mathematics (cs.DM)
Applied Mathematics
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
Discrete Mathematics and Combinatorics
[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS]
Computer Science - Discrete Mathematics
MathematicsofComputing_DISCRETEMATHEMATICS
Subjects
Details
- Database :
- OpenAIRE
- Accession number :
- edsair.doi.dedup.....b389550cf116bbcc386b9ee733ea07d0
- Full Text :
- https://doi.org/10.48550/arxiv.1710.02013