CYCLE STRUCTURE OF EDGE LABELLED GRAPHS
- Authors
- 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
Document 1 of 1
- Date modified: