1. Research UNE
  2. UNE
  3. Journal Article
Please use this identifier to cite or link to this item: https://hdl.handle.net/1959.11/63369
Full metadata record
DC FieldValueLanguage
dc.contributor.authorBrankovic, Ljiljanaen
dc.contributor.authorMiller, Mirkaen
dc.contributor.authorSiran, Jozefen
dc.date.accessioned2024-10-09T00:26:36Z-
dc.date.available2024-10-09T00:26:36Z-
dc.date.issued1996-12-
dc.identifier.citationCongressus Numerantium: a conference journal on numerical themes, v.120, p. 169-182en
dc.identifier.issn0384-9864en
dc.identifier.issn0384-997Xen
dc.identifier.urihttps://hdl.handle.net/1959.11/63369-
dc.description.abstract<p>The motivation for this work comes from a security problem of statistical databases: In a database of n records, given k SUM queries, is it possible to answer all of them, plus another (\2)) —k distinct SUM queries, in such a way that no individual value from the database is revealed?</p> <p>The corresponding mathematical problem (stated in terms of certain extensions of 0-1 matrices) is known to be NP-complete in general. We show that it remains NP-complete even when restricted to the case when each query involves four records and each record is in at most three queries. On the other hand, we identify certain cases in which the problem is solvable in polynomial time. The case when every record is contained in at most two of the given k queries is studied in detail from the graph-theoretic point of view.</p>en
dc.languageenen
dc.publisherUtilitas Mathematica Publishing Incen
dc.relation.ispartofCongressus Numerantium: a conference journal on numerical themesen
dc.titleGraphs, 0-1 Matrices, and Usability of Statistical Databasesen
dc.typeJournal Articleen
local.contributor.firstnameLjiljanaen
local.contributor.firstnameMirkaen
local.contributor.firstnameJozefen
local.profile.schoolSchool of Science and Technologyen
local.profile.emaillbrankov@une.edu.auen
local.output.categoryC1en
local.record.placeauen
local.record.institutionUniversity of New Englanden
local.publisher.placeCanadaen
local.format.startpage169en
local.format.endpage182en
local.peerreviewedYesen
local.identifier.volume120en
local.contributor.lastnameBrankovicen
local.contributor.lastnameMilleren
local.contributor.lastnameSiranen
dc.identifier.staffune-id:lbrankoven
local.profile.orcid0000-0002-5056-4627en
local.profile.roleauthoren
local.profile.roleauthoren
local.profile.roleauthoren
local.identifier.unepublicationidune:1959.11/63369en
dc.identifier.academiclevelAcademicen
dc.identifier.academiclevelAcademicen
dc.identifier.academiclevelAcademicen
local.title.maintitleGraphs, 0-1 Matrices, and Usability of Statistical Databasesen
local.relation.fundingsourcenotePart of the research of the third author has been done while visiting the Department of Computer Science of the University of Newcastle, NSW, Australia, supported by RMC visitor grant.en
local.output.categorydescriptionC1 Refereed Article in a Scholarly Journalen
local.relation.urlhttps://combinatorialpress.com/cn/archive/en
local.search.authorBrankovic, Ljiljanaen
local.search.authorMiller, Mirkaen
local.search.authorSiran, Jozefen
local.uneassociationNoen
local.atsiresearchNoen
local.sensitive.culturalNoen
local.year.published1996en
local.fileurl.closedpublishedhttps://rune.une.edu.au/web/retrieve/97075662-c2d2-49dd-a271-178851fd5fbcen
local.subject.for2020490404 Combinatorics and discrete mathematics (excl. physical combinatorics)en
local.subject.for2020460402 Data and information privacyen
local.subject.seo2020280115 Expanding knowledge in the information and computing sciencesen
local.subject.seo2020220405 Cybersecurityen
local.profile.affiliationtypePre-UNEen
local.profile.affiliationtypeExternal Affiliationen
local.profile.affiliationtypeExternal Affiliationen
Appears in Collections:Journal Article
School of Science and Technology
Files in This Item:
1 files
File SizeFormat 
Show simple item record
Google Media

Google ScholarTM

Check


Items in Research UNE are protected by copyright, with all rights reserved, unless otherwise indicated.