Signed graphs are graphs with an assignment of a positive or a negative sign to each edge. These graphs are helpful to represent different types of networks. For instance, they have been used in social networks, where a positive sign in an edge represents friendship between the two endpoints of that edge, while a negative sign represents enmity. Given a signed graph, an important question is how to embed such a graph in a metric space so that in the embedding every vertex is closer to its positive neighbors than to its negative ones. This problem is known as Sitting Arrangement (SA) problem and it was introduced by Kermarrec et al. (Proceedings of the 36th International Symposium on Mathematical Foundations of Computer Science (MFCS), pp. 388–399, 2011). Cygan et al. (Proceedings of the 37th International Symposium on Mathematical Foundations of Computer Science (MFCS), 2012) proved that the decision version of SA problem is NP-Complete when the signed graph has to be embedded into the Euclidean line. In this work, we study the minimization version of SA (MinSA) problem in the Euclidean line. We relate MinSA problem to the well known quadratic assignment (QA) problem. We establish such a relation by proving that local minimums in MinSA problem are equivalent to local minimums in a particular case of QA problem. In this document, we design two heuristics based on the combinatorial structure of MinSA problem. We experimentally compare their performances against heuristics designed for QA problem. This comparison favors the proposed heuristics.

Pardo, E., Soto, M., Thraves, C. (2013). Embedding signed graphs in the line: Heuristics to solve MinSA problem. JOURNAL OF COMBINATORIAL OPTIMIZATION, 29(2), 451-471 [10.1007/s10878-013-9604-1].

Embedding signed graphs in the line: Heuristics to solve MinSA problem

Soto, Mauricio
;
2013

Abstract

Signed graphs are graphs with an assignment of a positive or a negative sign to each edge. These graphs are helpful to represent different types of networks. For instance, they have been used in social networks, where a positive sign in an edge represents friendship between the two endpoints of that edge, while a negative sign represents enmity. Given a signed graph, an important question is how to embed such a graph in a metric space so that in the embedding every vertex is closer to its positive neighbors than to its negative ones. This problem is known as Sitting Arrangement (SA) problem and it was introduced by Kermarrec et al. (Proceedings of the 36th International Symposium on Mathematical Foundations of Computer Science (MFCS), pp. 388–399, 2011). Cygan et al. (Proceedings of the 37th International Symposium on Mathematical Foundations of Computer Science (MFCS), 2012) proved that the decision version of SA problem is NP-Complete when the signed graph has to be embedded into the Euclidean line. In this work, we study the minimization version of SA (MinSA) problem in the Euclidean line. We relate MinSA problem to the well known quadratic assignment (QA) problem. We establish such a relation by proving that local minimums in MinSA problem are equivalent to local minimums in a particular case of QA problem. In this document, we design two heuristics based on the combinatorial structure of MinSA problem. We experimentally compare their performances against heuristics designed for QA problem. This comparison favors the proposed heuristics.
Articolo in rivista - Articolo scientifico
Graph drawing; Graph embedding; Heuristics; Quadratic assignment problem; Signed graphs; Computer Science Applications1707 Computer Vision and Pattern Recognition; Discrete Mathematics and Combinatorics; Control and Optimization; Computational Theory and Mathematics; Applied Mathematics
English
451
471
21
Pardo, E., Soto, M., Thraves, C. (2013). Embedding signed graphs in the line: Heuristics to solve MinSA problem. JOURNAL OF COMBINATORIAL OPTIMIZATION, 29(2), 451-471 [10.1007/s10878-013-9604-1].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/220903
Citazioni
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 5
Social impact