Relabeling nodes according to the structure of the graph

Ronan Hamon (1) , Céline Robardet (2) , Pierre Borgnat (1) , Patrick Flandrin (1)

1 Phys-ENS - Laboratoire de Physique de l'ENS Lyon
2 LIRIS - Laboratoire d'InfoRmatique en Image et Systèmes d'information

In this paper we introduce a new algorithm to find a approximate solution for cyclic bandwidth sum problem (CBSP). This problem consists in a minimization of the sum of the distances in the numbering between pairs of vertices connected by a edge. A method based on a depth-first search is proposed where the order in which the nodes are traversed depends on a criterion based on the the Jaccard index between the current node and its neighbors. This method is faster and more effective than the other available heuristics.

Domaines: Traitement du signal et de l'image [eess.SP]; Traitement du signal et de l'image [eess.SP]

Ronan Hamon, Céline Robardet, Pierre Borgnat, Patrick Flandrin. Relabeling nodes according to the structure of the graph. 2013. ⟨ensl-00878041⟩