<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

Publié en ligne: 21 janv. 2020

Pages: 131 - 141

Reçu: 26 sept. 2019

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

Mots clés
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

Publié en ligne: 21 janv. 2020

Pages: 131 - 141

Reçu: 26 sept. 2019

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

Mots clésclique 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.

Mots clés
clique number, maximum clique, branching rules