CRIS

Permanent URI for this communityhttps://investigadores.udd.cl/handle/123456789/1

Browse

Settings

Access type: UnknownSubject: search.filters.subject.heuristic algorithms

Search Results

Now showing 1 - 2 of 2
  • Loading...
    Thumbnail Image
    Some of the metrics are blocked by your 
    consent settings
    Item type:Publication,
    Total Outer-Independent Domination Number: Bounds and Algorithms
    (MDPI AG, 2025-03-10)
    BOSCH PÉREZ, PAUL JESÚS  
    ;
    Ernesto Parra Inza
    ;
    Ismael Rios Villamar
    ;
    José Luis Sánchez-Santiesteban
    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 γtoi(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 lower and upper bounds for γtoi(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.
      3
  • Loading...
    Thumbnail Image
    Some of the metrics are blocked by your 
    consent settings
    Item type:Publication,
    A New Genetic Algorithm Encoding for Coalition Structure Generation Problems
    (2020)
    Juan Pablo Contreras
    ;
    BOSCH PÉREZ, PAUL JESÚS  
    ;
    VARAS VALDÉS, MAURICIO ANDRÉS  
    ;
    Franco Basso
    Genetic algorithms have proved to be a useful improvement heuristic for tackling several combinatorial problems, including the coalition structure generation problem. In this case, the focus lies on selecting the best partition from a discrete set. A relevant issue when designing a Genetic algorithm for coalition structure generation problems is to choose a proper genetic encoding that enables an efficient computational implementation. In this paper, we present a novel hybrid encoding, and we compare its performance against several genetic encoding proposed in the literature. We show that even in difficult instances of the coalition structure generation problem, the proposed approach is a competitive alternative to obtaining good quality solutions in reasonable computing times. Furthermore, we also show that the encoding relevance increases as the number of players increases.
    Scopus© Citations 12  1