Termination of the Iterated Strong-Factor Operator on Multipartite Graphs - Archive ouverte HAL Access content directly
Journal Articles Theoretical Computer Science Year : 2015

Termination of the Iterated Strong-Factor Operator on Multipartite Graphs

(1) , (2) , (3, 4)
1
2
3
4

Abstract

The clean-factor operator is a multipartite graph operator that has been introduced in the context of complex network modelling. Here, we consider a less constrained variation of the clean-factor operator, named strong-factor operator, and we prove that, as for the clean-factor operator, the iteration of the strong-factor operator always terminates, independently of the graph given as input. Obtaining termination for all graphs using minimal constraints on the definition of the operator is crucial for the modelling purposes for which the clean-factor operator has been introduced. Moreover we show that the relaxation of constraints we operate not only preserves termination but also preserves the termination time, in the sense that the strong-factor series always terminates before the clean-factor series. In addition to those results, we answer an open question from Latapy et al. [12] by showing that the iteration of the factor operator, which is a proper relaxation of both operators mentioned above, does not always terminate.

Dates and versions

hal-01241925 , version 1 (11-12-2015)

Identifiers

Cite

Christophe Crespelle, Thi Ha Duong Phan, Hung Tran-The. Termination of the Iterated Strong-Factor Operator on Multipartite Graphs. Theoretical Computer Science, 2015, 571, pp.67-77. ⟨10.1016/j.tcs.2015.01.009⟩. ⟨hal-01241925⟩
110 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More