Title

Complexity Of A Proposed Database Storage Structure

Comments

Authors: contact us about adding a copy of your work at STARS@ucf.edu

Abbreviated Journal Title

Inf. Syst.

Keywords

Computer Science; Information Systems

Abstract

An alternate method for storing M to N relationships is presented. Implementing this method involves a minimization procedure which is shown to be equivalent to finding the minimal number of bipartite cliques which cover all of the edges of a related bipartite graph. This bipartite edge clique cover problem is known to be NP-complete, suggesting that attention should be focused on finding heuristic, not necessarily optimal, algorithms which produce solutions in polynomial-time. One such heuristic is presented which seems to work well on a variety of bipartite graphs. However, there are bipartite graphs for which its performance is poor, i.e. the heuristic produces solutions significantly worse than optimum. A family of bipartite graphs is presented for which the performance factor is unbounded.

Journal Title

Information Systems

Volume

6

Issue/Number

1

Publication Date

1-1-1980

Document Type

Article

Language

English

First Page

47

WOS Identifier

WOS:A1981LS47100004

ISSN

0306-4379

Share

COinS