Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
Balancing a Complete Signed Graph by Editing Edges and Deleting Nodes
verfasst von : Bang Ye Wu, Jia-Fen Chen
Erschienen in: Advances in Intelligent Systems and Applications - Volume 1
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
A signed graph is a simple undirected graph in which each edge is either positive or negative. A signed graph is balanced if every cycle has even numbers of negative edges. In this paper we study the problem of balancing a complete signed graph by minimum editing cost, in which the editing operations includes inserting edges, deleting edges, and deleting nodes. We design a branch-and-bound algorithm, as well as a heuristic algorithm. By experimental results we show that the branch-and-bound algorithm is much efficient than a trivial one and the heuristic algorithm performs well.