Minimal linear invariants

Ming Yang Kao*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations


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.

Original languageEnglish (US)
Title of host publicationAlgorithms, Concurrency and Knowledge - 1995 Asian Computing Science Conference, ACSC 1995, Proceedings
EditorsKanchana Kanchanasut, Jean-Jacques Levy
PublisherSpringer Verlag
Number of pages11
ISBN (Print)3540606882, 9783540606888
StatePublished - 1995
EventAsian Computing Science Conference, ACSC 1995 - Pathumthani, Thailand
Duration: Dec 11 1995Dec 13 1995

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


OtherAsian Computing Science Conference, ACSC 1995

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Minimal linear invariants'. Together they form a unique fingerprint.

Cite this