A simple algorithm to detect balance in signed graphs

DOI10.1016/0165-4896(80)90010-4zbMath0497.05056MaRDI QIDQ1170207

Frank Harary, Jerald A. Kabell

Publication date: 1980

Published in: Mathematical Social Sciences (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/2027.42/23150

zbMATH Keywords

graph algorithm; spanning tree; fundamental cycles; balanced signed graph

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C38: Paths and cycles

05C99: Graph theory

Related Items

Further Algebraic Results in the Theory of Balance, A Dynamic Programming Algorithm To Test A Signed Graph For Balance, How colorful the signed graph?, Applications of edge coverings by cliques, Signsolvability revisited, An algorithm for identifying Morishima and anti-Morishima matrices and balanced digraphs, Graph theoretic models, The line index and minimum cut of weighted graphs, Extracting pure network submatrices in linear programs using signed graphs., On the problem of consistent marking of a graph, Characterizations of consistent marked graphs, Inverting Signed Graphs

Cites Work

• Consistency in marked digraphs
• Parallel concepts in graph theory
• On the computational power of pushdown automata
• On the notion of balance of a signed graph
• Counting balanced signed graphs using marked graphs
• Consistent graphs with signed points