article · International Journal of Computer Mathematics · 2003
A Dynamic Programming Algorithm To Test A Signed Graph For Balance
Cited by 7Abstract and details only
Abstract
A signed graph H =( V , E , σ ) consists of a graph G =( V , E ) together with a sign function σ : E M { m , +}. A fundamental concept in both, the theory and applications of signed graphs is that of balance . We present a new dynamic programming algorithm to detect balance in signed graphs which traverses each line of the signed graph at most once. Furthermore the computer implementation of the proposed algorithm requires three linear arrays of length | V | only, and the graph need not be stored in computer's memory. Thus the proposed algorithm is optimal with respect to both time and space complexities: The line index for balance of an unbalanced signed graph is the minimum number of lines needed to be removed to make the signed graph balanced. Barahona has proved that finding the line index for balance of a signed graph is an NP- complete problem. In this paper, we prove a stronger result, namely that the problem remains NP- complete even when restricted to signed graphs having negative signs only.
Cite this paper
Loukakis, E. (2003). A Dynamic Programming Algorithm To Test A Signed Graph For Balance. International Journal of Computer Mathematics, 80(4), 499–507. https://doi.org/10.1080/0020716021000009246
Loukakis, E. “A Dynamic Programming Algorithm To Test A Signed Graph For Balance.” International Journal of Computer Mathematics, vol. 80, no. 4, 2003, pp. 499–507, https://doi.org/10.1080/0020716021000009246.
Loukakis, E. 2003. “A Dynamic Programming Algorithm To Test A Signed Graph For Balance.” International Journal of Computer Mathematics 80 (4): 499–507. https://doi.org/10.1080/0020716021000009246.
Loukakis, E. (2003) ‘A Dynamic Programming Algorithm To Test A Signed Graph For Balance’, International Journal of Computer Mathematics, 80(4), pp. 499–507. Available at: https://doi.org/10.1080/0020716021000009246.
@article{loukakis2003dynamic,
title = {{A Dynamic Programming Algorithm To Test A Signed Graph For Balance}},
author = {Loukakis, E.},
journal = {International Journal of Computer Mathematics},
volume = {80},
number = {4},
pages = {499--507},
year = {2003},
doi = {10.1080/0020716021000009246}
}Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.