TY - GEN

T1 - Minimal linear invariants

AU - Kao, Ming Yang

N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1995.

PY - 1995

Y1 - 1995

N2 - 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. Because of this uniqueness~ the information contained in a linear invariant is not protected. The minimal linear invariants are the most basic units of unprotected information. This paper establishes a fundamental correspondence between minimal linear invariants of a table and minimal edge cuts of a graph constructed from the table. As one of several consequences of this correspondence, a linear-time algorithm is obtained to find a set of minimal linear invariants that completely characterize the linear invariant information contained in individual rows and columns.

AB - 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. Because of this uniqueness~ the information contained in a linear invariant is not protected. The minimal linear invariants are the most basic units of unprotected information. This paper establishes a fundamental correspondence between minimal linear invariants of a table and minimal edge cuts of a graph constructed from the table. As one of several consequences of this correspondence, a linear-time algorithm is obtained to find a set of minimal linear invariants that completely characterize the linear invariant information contained in individual rows and columns.

UR - http://www.scopus.com/inward/record.url?scp=21844526021&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=21844526021&partnerID=8YFLogxK

U2 - 10.1007/3-540-60688-2_32

DO - 10.1007/3-540-60688-2_32

M3 - Conference contribution

AN - SCOPUS:21844526021

SN - 3540606882

SN - 9783540606888

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 23

EP - 33

BT - Algorithms, Concurrency and Knowledge - 1995 Asian Computing Science Conference, ACSC 1995, Proceedings

A2 - Kanchanasut, Kanchana

A2 - Levy, Jean-Jacques

PB - Springer Verlag

T2 - Asian Computing Science Conference, ACSC 1995

Y2 - 11 December 1995 through 13 December 1995

ER -