Publication: Total Outer-Independent Domination Number: Bounds and Algorithms
| dc.contributor.author | Bosch, Paul | |
| dc.contributor.author | Parra Inza, Ernesto | |
| dc.contributor.author | Rios Villamar, Ismael | |
| dc.contributor.author | Sánchez-Santiesteban, José Luis | |
| dc.date.accessioned | 2026-10-05T21:00:02Z | |
| dc.date.available | 2026-10-05T21:00:02Z | |
| dc.date.issued | 2025 | |
| dc.description.abstract | In graph theory, the study of domination sets has garnered significant interest due to its applications in network design and analysis. Consider a graph G(V, E); a subset of its vertices is a total dominating set (TDS) if, for each x ∈ V(G), there exists an edge in E(G) connecting x to at least one vertex within this subset. If the subgraph induced by the vertices outside the TDS has no edges, the set is called a total outer-independent dominating set (TOIDS). The total outer-independent domination number, denoted as γoit (G), represents the smallest cardinality of such a set. Deciding if a given graph has a TOIDS with at most r vertices is an NP-complete problem. This study introduces new lowerand upper bounds for γoit (G) and presents an exact solution approach using integer linear programming (ILP). Additionally, we develop a heuristic and a procedure to efficiently obtain minimal TOIDS. | |
| dc.description.version | Versión publicada | |
| dc.format.extent | 18 p. | |
| dc.identifier.citation | Bosch, P., Parra Inza, E., Rios Villamar, I., & Sánchez-Santiesteban, J. L. (2025). Total Outer-Independent Domination Number: Bounds and Algorithms. Algorithms, 18(3), 159. https://doi.org/10.3390/a18030159 | |
| dc.identifier.doi | https://doi.org/10.3390/a18030159 | |
| dc.identifier.uri | https://hdl.handle.net/11447/11226 | |
| dc.language.iso | en | |
| dc.subject | Graph theory | |
| dc.subject | Total outer-independent dominating set | |
| dc.subject | Integer linear program | |
| dc.subject | Heuristic algorithm | |
| dc.subject | Time complexity | |
| dc.title | Total Outer-Independent Domination Number: Bounds and Algorithms | |
| dc.type | Article | |
| dcterms.accessRights | Acceso abierto | |
| dcterms.source | algorithms | |
| dspace.entity.type | Publication |