A Dynamic Programming Algorithm To Test A Signed Graph For Balance
A signed graph is a graph where every edge is assigned a value `\(-\)' or `\(+\)'. A signed graph \(G\) is balanced if every cycle in \(G\) is positive, i.e. has an even number of negative lines. Equivalently, any two paths between a pair of vertices in \(G\) have the same sign. Equivalently, the vertex set of \(G\) can be partitioned into two disjoint sets called coalitions, one of which may be empty, such that every positive line (edge) joins vertices of the same coalition and every negative line joins vertices of different coalitions. This paper presents a new dynamic programming algorithm to detect balance in signed graphs and which traverses each edge of the graph at most once. The line index for balance of an unbalanced signed graph is the minimum number of edges needed to be removed in order to make the signed graph balanced. Finding the line index for balance of a signed graph is NP-complete even if the graph has only negative signs.
- A characterization of signed hypergraphs and its applications to VLSI via minimization and logic synthesis
- A simple algorithm to detect balance in signed graphs
- Characterizations of signed graphs
- Edge-Deletion Problems
- scientific article; zbMATH DE number 3566474 (Why is no real title available?)
- scientific article; zbMATH DE number 3226832 (Why is no real title available?)
- On the notion of balance of a signed graph
- Signed graphs
- Some simplified NP-complete graph problems
- On optimization of complete social networks
- Approximation algorithms for balancing signed graphs
- Computing the line index of balance using integer programming optimisation
- scientific article; zbMATH DE number 996908 (Why is no real title available?)
- A Coding Approach to Signed Graphs
- Algorithms for derivation of structurally stable Hamiltonian signed graphs
- Further Algebraic Results in the Theory of Balance
This page was built for publication: A Dynamic Programming Algorithm To Test A Signed Graph For Balance
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4807702)