The membership problem for switching classes with skew gains

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)


Gain graphs are graphs in which each edge has a gain (a label from a group so that reversing the direction of an edge inverts the gain). In this paper we take a generalized view of gain graphs in which the gain of an edge is related to the gain of the reverse edge by an anti-involution, i.e., an anti-automorphism of order at most two. We call these skew gain graphs. Switching classes are equivalence classes of gain graphs under the switching operation. The membership (or equivalence) problem is important to the theory of switching classes. The problem is to decide for two given skew gain graphs, on the same underlying graph and having gains from the same group, whether or not they belong to the same switching class. We give efficient algorithms. If a certain skew gain graph in the switching class has only abelian gains, then we can reduce the membership problem to an elegant problem on anti-involutions. Finally we show that the word problem can be reduced to the general membership problem, thereby establishing undecidability of the latter for some groups.
Original languageEnglish
Pages (from-to)375-387
Number of pages13
JournalFundamenta Informaticae
Issue number4
Publication statusPublished - 1 Dec 1999


Dive into the research topics of 'The membership problem for switching classes with skew gains'. Together they form a unique fingerprint.

Cite this