A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Pivots, determinants, and perfect matchings of graphs
Tekijät: Brijder R, Harju T, Hoogeboom HJ
Kustantaja: ELSEVIER SCIENCE BV
Julkaisuvuosi: 2012
Journal: Theoretical Computer Science
Tietokannassa oleva lehden nimi: THEORETICAL COMPUTER SCIENCE
Lehden akronyymi: THEOR COMPUT SCI
Vuosikerta: 454
Aloitussivu: 64
Lopetussivu: 71
Sivujen määrä: 8
ISSN: 0304-3975
DOI: https://doi.org/10.1016/j.tcs.2012.02.031
Tiivistelmä
We consider sequences of local and edge complementations on graphs with loops (we allow local complementation only on looped vertices). We recall that these operations together form the matrix operation of principal pivot transform (or pivot) restricted to graphs. This fact is not well known, and as a consequence various special cases of the properties of pivot have been rediscovered multiple times. In this paper we give a gentle overview of various properties of pivot for local and edge complementations on graphs. Moreover, we relate the pivot operation to perfect matchings to obtain a purely graph-theoretical characterization of the effect of sequences of pivot operations. Finally, we show that two of the three operations that make up a formal graph model of the biological process of gene assembly in ciliates together form the matrix operation of Schur complement restricted to graphs. (C) 2012 Elsevier B.V. All rights reserved.
We consider sequences of local and edge complementations on graphs with loops (we allow local complementation only on looped vertices). We recall that these operations together form the matrix operation of principal pivot transform (or pivot) restricted to graphs. This fact is not well known, and as a consequence various special cases of the properties of pivot have been rediscovered multiple times. In this paper we give a gentle overview of various properties of pivot for local and edge complementations on graphs. Moreover, we relate the pivot operation to perfect matchings to obtain a purely graph-theoretical characterization of the effect of sequences of pivot operations. Finally, we show that two of the three operations that make up a formal graph model of the biological process of gene assembly in ciliates together form the matrix operation of Schur complement restricted to graphs. (C) 2012 Elsevier B.V. All rights reserved.
Turun yliopiston Tutkimustietojärjestelmän portaali