On the existence of an integral potential in a weighted bidirected graph

Research output: Contribution to journalArticleAcademicpeer-review

2 Citations (Scopus)
1 Downloads (Pure)

Abstract

A. Schrijver proved that if A denotes the incidence matrix of a bidirected graph, and b is an integral "length" function on the edges of A, then the system Axb has an integer solution x if and only if (i) each cycle in A has nonnegative length, and (ii) each doubly odd cycle in A has positive length. Unfortunately these cycles may be very complicated. We show that we may restrict conditions (i) and (ii) to a set of reasonably simple cycles.
Original languageEnglish
Pages (from-to)541-553
JournalLinear Algebra and Its Applications
Volume114-115
DOIs
Publication statusPublished - 1989

Fingerprint

Dive into the research topics of 'On the existence of an integral potential in a weighted bidirected graph'. Together they form a unique fingerprint.

Cite this