<abstract xmlns="http://www.w3.org/1999/xhtml"><p>In an earlier work [6] the concept of splitting partition of a graph was introduced in connection with the maximum clique problem. A splitting partition of a graph can be used to replace the graph by two smaller graphs in the course of a clique search algorithm. In other words splitting partitions can serve as a branching rule in an algorithm to compute the clique number of a given graph. In the paper we revisit this branching idea. We will describe a technique to construct not necessary optimal splitting partitions. The given graph can be viewed as a metric space and the geometry of this space plays a guiding role. In order to assess the performance of the procedure we carried out numerical experiments.</p></abstract>

In an earlier work [6] the concept of splitting partition of a graph was introduced in connection with the maximum clique problem. A splitting partition of a graph can be used to replace the graph by two smaller graphs in the course of a clique search algorithm. In other words splitting partitions can serve as a branching rule in an algorithm to compute the clique number of a given graph. In the paper we revisit this branching idea. We will describe a technique to construct not necessary optimal splitting partitions. The given graph can be viewed as a metric space and the geometry of this space plays a guiding role. In order to assess the performance of the procedure we carried out numerical experiments.

Metric space method for constructing splitting partitions of graphs

Acta Universitatis Sapientiae, Informatica

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

{"article-title":"Metric space method for constructing splitting partitions of graphs"}

In an earlier work [6] the concept of splitting partition of a graph was introduced in connection with the maximum clique problem. A splitting partition of a...

Metric space method for constructing splitting partitions of graphs

Pubblicato online: 21 gen 2020

Pagine: 131 - 141

Ricevuto: 26 set 2019

DOI: https://doi.org/10.2478/ausi-2019-0009

Parole chiave
clique number, maximum clique, branching rules

© 2019 Sándor Szabó, published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Metric space method for constructing splitting partitions of graphs

Pubblicato online: 21 gen 2020

Pagine: 131 - 141

Ricevuto: 26 set 2019

DOI: https://doi.org/10.2478/ausi-2019-0009

Parole chiaveclique number, maximum clique, branching rules

© 2019 Sándor Szabó, published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Parole chiave
clique number, maximum clique, branching rules