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/54504
Full metadata record
DC FieldValueLanguage
dc.contributor.authorBazgan, Cristinaen
dc.contributor.authorBrankovic, Ljiljanaen
dc.contributor.authorCasel, Katrinen
dc.contributor.authorFernau, Henningen
dc.contributor.authorJansen, Klausen
dc.contributor.authorKlein, Kim-Manuelen
dc.contributor.authorLampis, Michaelen
dc.contributor.authorLiedloff, Mathieuen
dc.contributor.authorMonnot, Jérômeen
dc.contributor.authorPaschos, Vangelis Then
local.source.editorEditor(s): Veli Mäkinen, Simon J Puglisi and Leena Salmelaen
dc.date.accessioned2023-04-04T01:26:10Z-
dc.date.available2023-04-04T01:26:10Z-
dc.date.issued2016-
dc.identifier.citationCombinatorial Algorithms: Proceedings of the 27th International Workshop on Combinatorial Algorithms, p. 241-252en
dc.identifier.isbn9783319445434en
dc.identifier.isbn9783319445427en
dc.identifier.isbn331944543Xen
dc.identifier.urihttps://hdl.handle.net/1959.11/54504-
dc.description.abstract<p>We consider Upper Domination, the problem of finding a maximum cardinality minimal dominating set in a graph. We show that this problem does not admit an n1-ϵ approximation for any ϵ>0, making it significantly harder than Dominating Set, while it remains hard even on severely restricted special cases, such as cubic graphs (APX-hard), and planar subcubic graphs (NP-hard). We complement our negative results by showing that the problem admits an O(Δ) approximation on graphs of maximum degree Δ, as well as an EPTAS on planar graphs. Along the way, we also derive essentially tight n1-1d upper and lower bounds on the approximability of the related problem Maximum Minimal Hitting Set on d-uniform hypergraphs, generalising known results for Maximum Minimal Vertex Cover.</p>en
dc.languageenen
dc.publisherSpringeren
dc.relation.ispartofCombinatorial Algorithms: Proceedings of the 27th International Workshop on Combinatorial Algorithmsen
dc.relation.ispartofseriesLecture Notes in Computer Scienceen
dc.titleUpper Domination: Complexity and Approximationen
dc.typeConference Publicationen
dc.relation.conferenceIWOCA 2016: 27th International Workshop on Combinatorial Algorithmsen
dc.identifier.doi10.1007/978-3-319-44543-4_19en
local.contributor.firstnameCristinaen
local.contributor.firstnameLjiljanaen
local.contributor.firstnameKatrinen
local.contributor.firstnameHenningen
local.contributor.firstnameKlausen
local.contributor.firstnameKim-Manuelen
local.contributor.firstnameMichaelen
local.contributor.firstnameMathieuen
local.contributor.firstnameJérômeen
local.contributor.firstnameVangelis Then
local.profile.schoolSchool of Science and Technologyen
local.profile.emaillbrankov@une.edu.auen
local.output.categoryE1en
local.record.placeauen
local.record.institutionUniversity of New Englanden
local.date.conference17th - 19th August, 2016en
local.conference.placeHelsinki, Finlanden
local.publisher.placeCham, Switzerlanden
local.format.startpage241en
local.format.endpage252en
local.series.issn1611-3349en
local.series.issn0302-9743en
local.series.number9843en
local.peerreviewedYesen
local.title.subtitleComplexity and Approximationen
local.contributor.lastnameBazganen
local.contributor.lastnameBrankovicen
local.contributor.lastnameCaselen
local.contributor.lastnameFernauen
local.contributor.lastnameJansenen
local.contributor.lastnameKleinen
local.contributor.lastnameLampisen
local.contributor.lastnameLiedloffen
local.contributor.lastnameMonnoten
local.contributor.lastnamePaschosen
dc.identifier.staffune-id:lbrankoven
local.profile.orcid0000-0002-5056-4627en
local.profile.roleauthoren
local.profile.roleauthoren
local.profile.roleauthoren
local.profile.roleauthoren
local.profile.roleauthoren
local.profile.roleauthoren
local.profile.roleauthoren
local.profile.roleauthoren
local.profile.roleauthoren
local.profile.roleauthoren
local.identifier.unepublicationidune:1959.11/54504en
local.date.onlineversion2016-08-09-
dc.identifier.academiclevelAcademicen
dc.identifier.academiclevelAcademicen
dc.identifier.academiclevelAcademicen
dc.identifier.academiclevelAcademicen
dc.identifier.academiclevelAcademicen
dc.identifier.academiclevelAcademicen
dc.identifier.academiclevelAcademicen
dc.identifier.academiclevelAcademicen
dc.identifier.academiclevelAcademicen
dc.identifier.academiclevelAcademicen
local.title.maintitleUpper Dominationen
local.output.categorydescriptionE1 Refereed Scholarly Conference Publicationen
local.conference.detailsIWOCA 2016: 27th International Workshop on Combinatorial Algorithms, Helsinki, Finland, 17th - 19th August, 2016en
local.search.authorBazgan, Cristinaen
local.search.authorBrankovic, Ljiljanaen
local.search.authorCasel, Katrinen
local.search.authorFernau, Henningen
local.search.authorJansen, Klausen
local.search.authorKlein, Kim-Manuelen
local.search.authorLampis, Michaelen
local.search.authorLiedloff, Mathieuen
local.search.authorMonnot, Jérômeen
local.search.authorPaschos, Vangelis Then
local.uneassociationNoen
dc.date.presented2016-08-18-
local.atsiresearchNoen
local.conference.venueUniversity of Helsinkien
local.sensitive.culturalNoen
local.year.available2016en
local.year.published2016en
local.year.presented2016en
local.subject.for2020461305 Data structures and algorithmsen
local.subject.seo2020229999 Other information and communication services not elsewhere classifieden
local.date.start2016-08-17-
local.date.end2016-08-19-
local.profile.affiliationtypeExternal Affiliationen
local.profile.affiliationtypePre-UNEen
local.profile.affiliationtypeExternal Affiliationen
local.profile.affiliationtypeExternal Affiliationen
local.profile.affiliationtypeExternal Affiliationen
local.profile.affiliationtypeExternal Affiliationen
local.profile.affiliationtypeExternal Affiliationen
local.profile.affiliationtypeExternal Affiliationen
local.profile.affiliationtypeExternal Affiliationen
local.profile.affiliationtypeExternal Affiliationen
local.relation.worldcathttps://www.worldcat.org/title/957123354en
Appears in Collections:Conference Publication
School of Science and Technology
Files in This Item:
2 files
File Description SizeFormat 
Show simple item record

SCOPUSTM   
Citations

8
checked on May 4, 2024

Page view(s)

300
checked on Jun 18, 2023

Download(s)

4
checked on Jun 18, 2023
Google Media

Google ScholarTM

Check

Altmetric


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