The Diclique Representation and Decomposition of Binary Relations

ABSTRACT

The binary relation is often a useful mathematical structure for representing simple relationships whose essence is a directed connection. To better aid in interpreting or storing a binary relation we suggest a diclique decomposition. A diclique of a binary relation R is defined as an ordered pair (I, O) such that I × O ⊆ R and (I, O) is maximal. In this paper, an algorithm is described for determining the dicliques of a binary relation; it is proved that the set of such dicliques has a nice algebraic structure. The algebraic structure is used to show how dicliques can be coalesced, the relationship between cliques and dicliques is discussed, and an algorithm for determining cliques from dicliques is described.

REFERENCES

• 1: IARkRY, :FRANK. Graph Theory. Addison-Wesley, Reading, Mass., 1969, p. 17.
• 2: I-IART~ANIS, J. On the state assignment problem for sequential machines I. IRE Trans. EC-IO (1961), 157-165.
• 3: HARTMANIS, J. On the state assignment problem for sequential machines II. IRE Trans. EC-IO (1961), 593-603.
• 4: MACLANE, S., AND BIRKHOFF, G. Algebra. Macmillan Company, London, 1967.
• 5: J. Gary Augustson , Jack Minker, An Analysis of Some Graph Theoretical Cluster Techniques, Journal of the ACM (JACM), v.17 n.4, p.571-588, Oct. 1970 [doi>10.1145/321607.321608]
• 6: Gordon D. Mulligan , D. G. Corneil, Corrections to Bierstone's Algorithm for Generating Cliques, Journal of the ACM (JACM), v.19 n.2, p.244-247, April 1972 [doi>10.1145/321694.321698]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Measurement, Performance, Theory, Verification