Data security equals graph connectivity

Ming Yang Kao*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

38 Scopus citations

Abstract

To protect sensitive information in a cross-tabulated table, it is a common practice to suppress some of the cells in the table. This paper investigates four levels of data security of a two-dimensional table concerning the effectiveness of this practice. These four levels of data security protect the information contained in, respectively, individual cells, individual rows and columns, several rows or columns as a whole, and a table as a whole. The paper presents efficient algorithms and NP-completeness results for testing and achieving these four levels of data security. All these complexity results are obtained by means of fundamental equivalences between the four levels of data security of a table and four types of connectivity of a graph constructed from that table.

Original languageEnglish (US)
Pages (from-to)87-100
Number of pages14
JournalSIAM Journal on Discrete Mathematics
Volume9
Issue number1
DOIs
StatePublished - Feb 1996

Keywords

  • Bipartite completeness
  • Bipartite-(k + 1)-connectivity
  • Graph theory
  • Linear algebra
  • Mixed graphs
  • Statistical tables
  • Strong connectivity

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint Dive into the research topics of 'Data security equals graph connectivity'. Together they form a unique fingerprint.

Cite this