TY - GEN
T1 - Minimal linear invariants
AU - Kao, Ming Yang
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1995.
Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.
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 -