Ricerc@Sapienza

We study the problem of estimating the size of a matching when the graph is revealed in a streaming fashion. Our results are multifold:1.We give a tight structural result relating the size of a maximum matching to the arboricityα of a graph, which has been one of the most studied graph parameters for matching algorithms in data streams. One of the implications is an algorithm that estimates the matching size up to a factor of (α+ 2) (1 + ε) using O~ (αn2 / 3) space in insertion-only graph streams and O~ (αn4 / 5) space in dynamic streams, where n is the number of nodes in the graph.

A graph G(V, E) is claw-free if no vertex has three pairwise non-adjacent neighbours. The maximum weight stable set (MWSS) problem in a claw-free graph is a natural generalization of the matching problem and has been shown to be polynomially solvable by Minty and Sbihi in 1980. In a remarkable paper, Faenza, Oriolo and Stauffer have shown that, in a two-step procedure, a claw-free graph can be first turned into a quasi-line graph by removing strips containing all the irregular nodes and then decomposed into {claw, net}-free strips and strips with stability number at most three.

This study contributes to the existing literature on tourism market segmentation by providing a new matching-clustering procedure that allows patterns of behaviours to be identified using repeated cross-sectional surveys. By extracting equivalent samples over time, the matching method allows inter-temporal cluster analyses to be performed so that a deeper insight into a phenomenon can be obtained beyond the traditional aggregate level of understanding.