Approximation Algorithm for the Minimum Hub Cover Set Problem
A subset <inline-formula> <tex-math notation="LaTeX">${\mathcal{ S}}\subseteq V$ </tex-math></inline-formula> of vertices of an undirected graph <inline-formula> <tex-math notation="LaTeX">$G=(V,E)$ </tex-math></inline-formula> is a...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2022-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/9771189/ |
| _version_ | 1811341899814928384 |
|---|---|
| author | Joel A. Trejo-Sanchez Candelaria E. Sansores-Perez Jesus Garcia-Diaz Jose Alberto Fernandez-Zepeda |
| author_facet | Joel A. Trejo-Sanchez Candelaria E. Sansores-Perez Jesus Garcia-Diaz Jose Alberto Fernandez-Zepeda |
| author_sort | Joel A. Trejo-Sanchez |
| collection | DOAJ |
| description | A subset <inline-formula> <tex-math notation="LaTeX">${\mathcal{ S}}\subseteq V$ </tex-math></inline-formula> of vertices of an undirected graph <inline-formula> <tex-math notation="LaTeX">$G=(V,E)$ </tex-math></inline-formula> is a hub cover when for each edge <inline-formula> <tex-math notation="LaTeX">$(u,v) \in E$ </tex-math></inline-formula>, at least one of its endpoints belongs to <inline-formula> <tex-math notation="LaTeX">${\mathcal{ S}}$ </tex-math></inline-formula>, or there exists a vertex <inline-formula> <tex-math notation="LaTeX">$r \in {\mathcal{ S}}$ </tex-math></inline-formula> that is a neighbor of both <inline-formula> <tex-math notation="LaTeX">$u$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$v$ </tex-math></inline-formula>. The problem of computing a minimum hub cover set in arbitrary graphs is NP-hard. This problem has applications for indexing large databases. This paper proposes <inline-formula> <tex-math notation="LaTeX">$\Psi $ </tex-math></inline-formula>-MHC, the first approximation algorithm for the minimum hub cover set in arbitrary graphs to the best of our knowledge. The approximation ratio of this algorithm is <inline-formula> <tex-math notation="LaTeX">$\ln \mu $ </tex-math></inline-formula>, where <inline-formula> <tex-math notation="LaTeX">$\mu $ </tex-math></inline-formula> is upper bounded by <inline-formula> <tex-math notation="LaTeX">$\min \left\{{\frac {1}{2}(\Delta +1)^{2}, \vert E\vert }\right\}$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$\Delta $ </tex-math></inline-formula> is the degree of <inline-formula> <tex-math notation="LaTeX">$G$ </tex-math></inline-formula>. The execution time of <inline-formula> <tex-math notation="LaTeX">$\Psi $ </tex-math></inline-formula>-MHC is <inline-formula> <tex-math notation="LaTeX">$O((\Delta + 1) \vert E \vert + \vert {\mathcal{ S}} \vert \vert V \vert)$ </tex-math></inline-formula>. Experimental results show that <inline-formula> <tex-math notation="LaTeX">$\Psi $ </tex-math></inline-formula>-MHC far outperforms the theoretical approximation ratio for the input graph instances. |
| first_indexed | 2024-04-13T19:00:55Z |
| format | Article |
| id | doaj.art-027e7e354504435c9bf530e0001487a5 |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-04-13T19:00:55Z |
| publishDate | 2022-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-027e7e354504435c9bf530e0001487a52022-12-22T02:34:05ZengIEEEIEEE Access2169-35362022-01-0110514195142710.1109/ACCESS.2022.31736159771189Approximation Algorithm for the Minimum Hub Cover Set ProblemJoel A. Trejo-Sanchez0https://orcid.org/0000-0001-9326-7713Candelaria E. Sansores-Perez1Jesus Garcia-Diaz2https://orcid.org/0000-0001-6334-2305Jose Alberto Fernandez-Zepeda3https://orcid.org/0000-0002-7847-6362CONACYT—Center for Research in Mathematics, Carretera Sierra Papacal, Chuburna Puerto, Merida, MexicoDepartment of Basic Sciences and Engineering, Universidad del Caribe, Cancun, MexicoConsejo Nacional de Ciencia y Tecnologia, Mexico City, MexicoDepartment of Computer Science, CICESE Research Center, Ensenada, MexicoA subset <inline-formula> <tex-math notation="LaTeX">${\mathcal{ S}}\subseteq V$ </tex-math></inline-formula> of vertices of an undirected graph <inline-formula> <tex-math notation="LaTeX">$G=(V,E)$ </tex-math></inline-formula> is a hub cover when for each edge <inline-formula> <tex-math notation="LaTeX">$(u,v) \in E$ </tex-math></inline-formula>, at least one of its endpoints belongs to <inline-formula> <tex-math notation="LaTeX">${\mathcal{ S}}$ </tex-math></inline-formula>, or there exists a vertex <inline-formula> <tex-math notation="LaTeX">$r \in {\mathcal{ S}}$ </tex-math></inline-formula> that is a neighbor of both <inline-formula> <tex-math notation="LaTeX">$u$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$v$ </tex-math></inline-formula>. The problem of computing a minimum hub cover set in arbitrary graphs is NP-hard. This problem has applications for indexing large databases. This paper proposes <inline-formula> <tex-math notation="LaTeX">$\Psi $ </tex-math></inline-formula>-MHC, the first approximation algorithm for the minimum hub cover set in arbitrary graphs to the best of our knowledge. The approximation ratio of this algorithm is <inline-formula> <tex-math notation="LaTeX">$\ln \mu $ </tex-math></inline-formula>, where <inline-formula> <tex-math notation="LaTeX">$\mu $ </tex-math></inline-formula> is upper bounded by <inline-formula> <tex-math notation="LaTeX">$\min \left\{{\frac {1}{2}(\Delta +1)^{2}, \vert E\vert }\right\}$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$\Delta $ </tex-math></inline-formula> is the degree of <inline-formula> <tex-math notation="LaTeX">$G$ </tex-math></inline-formula>. The execution time of <inline-formula> <tex-math notation="LaTeX">$\Psi $ </tex-math></inline-formula>-MHC is <inline-formula> <tex-math notation="LaTeX">$O((\Delta + 1) \vert E \vert + \vert {\mathcal{ S}} \vert \vert V \vert)$ </tex-math></inline-formula>. Experimental results show that <inline-formula> <tex-math notation="LaTeX">$\Psi $ </tex-math></inline-formula>-MHC far outperforms the theoretical approximation ratio for the input graph instances.https://ieeexplore.ieee.org/document/9771189/Approximation algorithmsheuristicsminimum hub cover setoptimization |
| spellingShingle | Joel A. Trejo-Sanchez Candelaria E. Sansores-Perez Jesus Garcia-Diaz Jose Alberto Fernandez-Zepeda Approximation Algorithm for the Minimum Hub Cover Set Problem IEEE Access Approximation algorithms heuristics minimum hub cover set optimization |
| title | Approximation Algorithm for the Minimum Hub Cover Set Problem |
| title_full | Approximation Algorithm for the Minimum Hub Cover Set Problem |
| title_fullStr | Approximation Algorithm for the Minimum Hub Cover Set Problem |
| title_full_unstemmed | Approximation Algorithm for the Minimum Hub Cover Set Problem |
| title_short | Approximation Algorithm for the Minimum Hub Cover Set Problem |
| title_sort | approximation algorithm for the minimum hub cover set problem |
| topic | Approximation algorithms heuristics minimum hub cover set optimization |
| url | https://ieeexplore.ieee.org/document/9771189/ |
| work_keys_str_mv | AT joelatrejosanchez approximationalgorithmfortheminimumhubcoversetproblem AT candelariaesansoresperez approximationalgorithmfortheminimumhubcoversetproblem AT jesusgarciadiaz approximationalgorithmfortheminimumhubcoversetproblem AT josealbertofernandezzepeda approximationalgorithmfortheminimumhubcoversetproblem |