CYCLE STRUCTURE OF EDGE LABELLED GRAPHS

Authors
  1. Diamond, J.S.
  2. Mendelzon, A.O.
Corporate Authors
Defence Research Establishment Atlantic, Dartmouth NS (CAN);Toronto Univ, Toronto ONT (CAN) Dept of Computer Science
Abstract
In this paper we examine the cyclic structure of graphs with edges labelled by elements of a partial order under the operation of deleting any edge whose label is less than or equal to all labels of edges of some cycle containing that edge. We show that all graphs obtained after repeating the above operations as many times as possible have similar structure with respect to the number of edges remaining and thus, in particular, the presence or absence of cycles. To show this, we apply some results of matroid theory. We also give an efficient algorithm to determine whether or not the resulting graph is acyclic. As an application to relational database theory, we show how this algorithm can be combined with a new characterization of database acyclicity to determine the cyclicity of a relational database scheme.
Date of publication
02 Nov 1990
Number of Pages
12
Reprinted from
Discrete Applied Mathematics, vol 45, 1993, p 51-62
DSTKIM No
94-00368
CANDIS No
136989
Format(s):
Hardcopy;Originator's fiche received by DSIS

Permanent link

Document 1 of 1

Date modified: