1. Research UNE
  2. UNE
  3. Conference Publication
Please use this identifier to cite or link to this item: https://hdl.handle.net/1959.11/63391
Full metadata record
DC FieldValueLanguage
dc.contributor.authorBrankovic, Ljiljanaen
dc.contributor.authorFernau, Henningen
local.source.editorEditor(s): Joe Ryan, Prabhu Manyem, Kiki Sugeng and Mirka Milleren
dc.date.accessioned2024-10-09T22:24:29Z-
dc.date.available2024-10-09T22:24:29Z-
dc.date.issued2005-09-
dc.identifier.citationProceedings of the Sixteenth Australasian Workshop on Combinatorial Algorithms (AWOCA 2005), p. 39-45en
dc.identifier.isbn0646452525en
dc.identifier.urihttps://hdl.handle.net/1959.11/63391-
dc.description.abstract<p>Weconsider the following combinatorial problem: given an <i>n</i> x <i>m</i> {0,1}-matrix M, find a minimum cardinality set S of mergings between neighboring rows or columns that yields an all-zeros matrix. Here, merging means performing a component-wise AND operation. We prove that this NP-hard minimization problem is factor-2-approximable by relating it to the VERTEX COVER problem on bipartite graphs.</p>en
dc.languageenen
dc.publisherUniversity of Ballaraten
dc.relation.ispartofProceedings of the Sixteenth Australasian Workshop on Combinatorial Algorithms (AWOCA 2005)en
dc.titleApproximability of a {0,1}-matrix Problemen
dc.typeConference Publicationen
dc.relation.conferenceAWOCA 2005: Sixteenth Australasian Workshop on Combinatorial Algorithmsen
local.contributor.firstnameLjiljanaen
local.contributor.firstnameHenningen
local.relation.isfundedbyARCen
local.profile.schoolSchool of Science and Technologyen
local.profile.emaillbrankov@une.edu.auen
local.output.categoryE1en
local.grant.numberDP0452182en
local.record.placeauen
local.record.institutionUniversity of New Englanden
local.date.conference18th - 21st September, 2005en
local.conference.placeBallarat, Australiaen
local.publisher.placeBallarat, Australiaen
local.format.startpage39en
local.format.endpage45en
local.peerreviewedYesen
local.contributor.lastnameBrankovicen
local.contributor.lastnameFernauen
dc.identifier.staffune-id:lbrankoven
local.profile.orcid0000-0002-5056-4627en
local.profile.roleauthoren
local.profile.roleauthoren
local.identifier.unepublicationidune:1959.11/63391en
dc.identifier.academiclevelAcademicen
dc.identifier.academiclevelAcademicen
local.title.maintitleApproximability of a {0,1}-matrix Problemen
local.output.categorydescriptionE1 Refereed Scholarly Conference Publicationen
local.relation.grantdescriptionARC/DP0452182en
local.conference.detailsAWOCA 2005: Sixteenth Australasian Workshop on Combinatorial Algorithms, Ballarat, Australia, 18th - 21st September, 2005en
local.search.authorBrankovic, Ljiljanaen
local.search.authorFernau, Henningen
local.uneassociationNoen
local.atsiresearchNoen
local.conference.venueUniversity of Ballaraten
local.sensitive.culturalNoen
local.year.published2005-
local.fileurl.closedpublishedhttps://rune.une.edu.au/web/retrieve/b2250fc9-c1f4-4318-99b7-e200c0117327en
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.date.start2005-09-18-
local.date.end2005-09-21-
local.profile.affiliationtypeExternal Affiliationen
local.profile.affiliationtypeExternal Affiliationen
Appears in Collections:Conference Publication
School of Science and Technology
Files in This Item:
2 files
File Description 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.