Publicación

Tipo de publicación: Artículos científicos (Publicados en revistas de divulgación o científicas)

Título del artículo: A fast approximation algorithm for the maximum 2?packing set problem on planar graphs

Registrado por: Journal of Optimization Letters

Año de publicación: 2023

Resumen: Given an undirected graph G = (V, E), a subset S ? V is a 2-packing set if, for any
pair of vertices u, v ? S, the shortest path between them is at least three-edge long.
Finding a 2-packing set of maximum cardinality is an NP-hard problem for arbitrary
graphs. This paper proposes an approximation algorithm for the maximum 2-packing set problem for planar graphs. We show that our algorithm is at least lambda?2/lambda
of the
optimal , where lambda is a constant related to how the
proposed algorithm decomposes the input graph into smaller subgraphs. Then, we
improve the solution given by our approximation algorithm by adding some vertices
to the solution. Experimentally, we show that our improved algorithm computes a
near-optimal 2-packing set. This algorithm is the frst approximation algorithm for
the maximum 2-packing set to the best of our knowledge.

Editorial:

Número de páginas:

Autor(es): Joel Antonio Trejo?Sánchez, Francisco A. Madera?Ramírez, José Alberto Fernández?Zepeda, José Luis López?Martínez, Alejandro Flores?Lamas

Campo: Computación

Disciplina: Ciencias de la Computación

Subdisciplina: Teoría de Grafos

Número de registro: https://doi.org/10.1007/s11590-022-01939-w