Jump to Main Content
PubAg
Main content area
An Optimal Algorithm to Detect Sign Compatibility of a Given Sigraph
 Author:
 Sinha, Deepa, Sethi, Anshu
 Source:
 National Academy science letters 2015 v.38 no.3 pp. 235238
 ISSN:
 0250541X
 Subject:
 algorithms, equations, mathematical theory
 Abstract:
 A [Formula: see text] (or [Formula: see text] in short) [Formula: see text] is a graph [Formula: see text] in which each edge [Formula: see text] carries a value [Formula: see text] called its [Formula: see text] denoted specially as [Formula: see text]. A sigraph [Formula: see text] is [Formula: see text] if there exists a marking [Formula: see text] of its vertices such that the end vertices of every negative edge receive ‘’ signs in [Formula: see text] and no positive edge in [Formula: see text] has both of its ends assigned ‘’ sign in [Formula: see text]. In this paper, we write algorithms to detect signcompatibility of a given sigraph and obtain optimal algorithm with complexity [Formula: see text].
 Agid:
 4407911

http://dx.doi.org/10.1007/s4000901403175