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.
ASJC Scopus subject areas
- Computer Science Applications
- Discrete Mathematics and Combinatorics
- Control and Optimization
- Computational Theory and Mathematics
- Applied Mathematics