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. 235-238
ISSN:
0250-541X
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 sign-compatibility of a given sigraph and obtain optimal algorithm with complexity [Formula: see text].
Agid:
4407911