Algorithm to find a maximum 2-packing set in a cactus
| Autor: | José Alberto Fernández-Zepeda, Alejandro Flores-Lamas, Joel Antonio Trejo-Sánchez |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
General Computer Science
Frequency assignment 020206 networking & telecommunications 0102 computer and information sciences 02 engineering and technology 01 natural sciences Graph Theoretical Computer Science Planar graph symbols.namesake 010201 computation theory & mathematics Shortest path problem Cactus 0202 electrical engineering electronic engineering information engineering symbols Algorithm Time complexity Connectivity MathematicsofComputing_DISCRETEMATHEMATICS Mathematics Network model |
| Zdroj: | Theoretical Computer Science. 725:31-51 |
| ISSN: | 0304-3975 |
| Popis: | In this paper, we address the problem of finding a maximum 2-packing set in a cactus. Let G = ( V G , E G ) be an undirected connected graph; then a subset S ⊆ V G is a 2-packing set if for every pair of vertices u , v ∈ S , the shortest path between them is at least three edges long. This type of sets results in a wide range of applications such as the study of molecules, network modeling, allocation of facilities, and frequency assignment. The cactus is a planar graph such that any edge belongs to at most one cycle. Hitherto, to the best of the authors' knowledge, no algorithm finds a maximum 2-packing set in a cactus. This problem is NP-Hard in arbitrary graphs. Our approach to solving this problem was first finding a maximum 2-packing set in a unicyclic graph. Then, we adapted this algorithm to run in a cactus. The time complexity of the resulting algorithm is O ( n 2 ) , where n = | V G | . |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect