Efficient edge domination problems in graphs
| Autor: | Naveed A. Sherwani, Dana L. Grinstead, Peter J. Slater, Nancy D. Holmes |
|---|---|
| Rok vydání: | 1993 |
| Předmět: |
Discrete mathematics
1-planar graph Edge cover Edge dominating set Computer Science Applications Theoretical Computer Science Combinatorics Indifference graph Chordal graph Dominating set Independent set Signal Processing Maximal independent set MathematicsofComputing_DISCRETEMATHEMATICS Information Systems Mathematics |
| Zdroj: | Information Processing Letters. 48:221-228 |
| ISSN: | 0020-0190 |
| DOI: | 10.1016/0020-0190(93)90084-m |
| Popis: | It has been shown, recently, that resource allocation problems in parallel processing systems can be viewed as edge domination problems in graphs. Other applications of edge domination include encoding theory and network routing problems. While the existence of efficient edge dominating sets in special classes of graphs such as paths and cycles can be determined in polynomial time, the complexity of the problem for general graphs remains open. In a graph G (V,E) , an edge uv ∈ E is said to dominate itself and any edge ux or vx where x ∈ V . A subset of edges E ′ ⊆ E is called an efficient edge dominating set for the graph G if all edges in E are dominated by exactly one edge of E ′. It is clear that not all graphs have efficient edge dominating sets. In fact, this is not even true for trees. In this paper, we show that the problem of determining if a graph G has an efficient edge dominating set is NP-complete for general graphs as well as for line graphs. However, in the case of series-parallel graphs, we show that the problem is polynomial. In fact, we present a linear-time algorithm for calculating the maximum number of edges that can be efficiently dominated in series-parallel graphs. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|