Back to Search
Start Over
Bumblebee visitation problem.
- Source :
-
Discrete Applied Mathematics . Oct2022, Vol. 319, p27-41. 15p. - Publication Year :
- 2022
-
Abstract
- Let G (V , E , c , w) be a weighted graph with vertex set V , edge set E , vertex-capacity function c : V → R + , and edge-weight function w : E → R + . In Bumblebee visitation problem , a mobile agent Bumblebee, denoted by B , begins by entering a vertex of the graph, and then moves along the edges of the graph. When B moves along an edge e = u v , both c (u) and c (v) are decreased by w (e). The Bumblebee visitation problem deals with placing and moving B in G such that the sum of the residual-capacities at the visited vertices is maximum. We consider four variants of this problem depending on edge-weights and constraints on the possible movements of B. The four variants are uniform-weight-constrained Bumblebee Visitation problem , variable-weight-constrained Bumblebee Visitation problem , uniform-weight-unconstrained Bumblebee Visitation problem , and variable-weight-unconstrained Bumblebee Visitation problem. We show that all four variants are NP-hard for general graphs, and the variable-weight constrained variant is NP-hard even for star graphs (K 1 , n). On the positive side, for the uniform-weight constrained variant, we give a dynamic programming based linear-time algorithm for trees and a quadratic-time algorithm for cactus. We then extend these algorithms for the variable-weight unconstrained variant. We also give a 3-factor approximation algorithm for the uniform-weight unconstrained variant where each vertex-capacity is at least five. [ABSTRACT FROM AUTHOR]
- Subjects :
- *APPROXIMATION algorithms
*WEIGHTED graphs
*DYNAMIC programming
*BUMBLEBEES
Subjects
Details
- Language :
- English
- ISSN :
- 0166218X
- Volume :
- 319
- Database :
- Academic Search Index
- Journal :
- Discrete Applied Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 158184673
- Full Text :
- https://doi.org/10.1016/j.dam.2022.01.007