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