Efficient detection and protection of information in cross tabulated tables II: Minimal linear invariants

Ming Yang Kao*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

To protect sensitive information in a cross tabulated table, it is a common practice to suppress some of the cells. A linear combination of the suppressed cells is called a linear invariant if it has a unique feasible value. Intuitively, the information contained in a linear invariant is not protected because its value can be uniquely determined. Using a decomposition approach, this paper establishes a fundamental correspondence between linear invariants of a table and edge cuts of a graph induced from the table. This correspondence is employed to give a linear-time algorithm for finding an important class of linear invariants called the row or column linear invariants. In subsequent papers, this correspondence is used to solve via graph theoretic techniques a wide variety of problems for protecting information in a table.

Original languageEnglish (US)
Pages (from-to)187-202
Number of pages16
JournalJournal of Combinatorial Optimization
Volume1
Issue number2
DOIs
StatePublished - Jan 1 1997

ASJC Scopus subject areas

  • Computer Science Applications
  • Discrete Mathematics and Combinatorics
  • Control and Optimization
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Efficient detection and protection of information in cross tabulated tables II: Minimal linear invariants'. Together they form a unique fingerprint.

Cite this