Advanced Search

Show simple item record

dc.contributor.authorDiner, Oznur Yasar
dc.contributor.authorGiannopoulou, Archontia C.
dc.contributor.authorStamoulis, Giannos
dc.contributor.authorThilikos, Dimitrios M.
dc.date.accessioned2023-10-19T15:12:47Z
dc.date.available2023-10-19T15:12:47Z
dc.date.issued2022
dc.identifier.issn0911-0119
dc.identifier.issn1435-5914
dc.identifier.urihttps://doi.org/10.1007/s00373-022-02513-y
dc.identifier.urihttps://hdl.handle.net/20.500.12469/5534
dc.description.abstractWe introduce the parameter of block elimination distance as a measure of how close a graph is to some particular graph class. Formally, given a graph class g, the class B(G) contains all graphs whose blocks belong to G and the class A(G) contains all graphs where the removal of a vertex creates a graph in G. Given a hereditary graph class G, we recursively define G((k)) so that G((0)) = B(G) and, if k >= 1 G((k)) B(A(G((k-1))) ) N We show that, for every nontrivial hereditary class g, the problem of deciding whether G is an element of G((k)) is NP-complete. We focus on the case where G is minor-closed and we study the minor obstruction set of G((k)) i.e., the minor-minimal graphs not in G((k)). We prove that the size of the obstructions of G((k)) is upper bounded by some explicit function ofk and the maximum size of a minor obstruction of G. This implies that the problem of deciding whether G is an element of G((k)) is constructively fixed parameter tractable, when parameterized by k. Finally, we give two graph operations that generate members of G((k)) from members of G((k -1)) and we prove that this set of operations is complete for the class O of outerplanar graphs.Please check and confirm if the authors Given and Family names have been correctly identified for author znur YaYar Diner. All authors names have been identified conectly. Please confirm if the corresponding author is correctly identified. Amend if necessary.This is correcten_US
dc.description.sponsorshipSpanish Agencia Estatal de Investigacion [MTM2017-82166-P]; ANR [ANR-16-CE40-0028, ANR-17-CE23-0010]; French-German Collaboration ANR/DFG [ANR-20-CE92-0027]en_US
dc.description.sponsorshipOznur Yasar Diner was supported by the Spanish Agencia Estatal de Investigacion under project MTM2017-82166-P. Giannos Stamoulis and Dimitrios M. Thilikos were supported by the ANR projects DEMOGRAPH (ANR-16-CE40-0028), ESIGMA (ANR-17-CE23-0010), and the French-German Collaboration ANR/DFG Project UTMA (ANR-20-CE92-0027)en_US
dc.language.isoengen_US
dc.publisherSpringer Japan Kken_US
dc.relation.ispartofGraphs and Combinatoricsen_US
dc.rightsinfo:eu-repo/semantics/openAccessen_US
dc.subjectGraph minorsen_US
dc.subjectBlock elimination distanceen_US
dc.subjectElimination distanceen_US
dc.subjectMinor obstructionsen_US
dc.subjectParameterized algorithmsen_US
dc.titleBlock Elimination Distanceen_US
dc.typearticleen_US
dc.authoridDiner, Öznur Yaşar/0000-0002-9271-2691
dc.authoridStamoulis, Giannos/0000-0002-4175-7793
dc.identifier.issue5en_US
dc.identifier.volume38en_US
dc.departmentN/Aen_US
dc.identifier.wosWOS:000836615400002en_US
dc.identifier.doi10.1007/s00373-022-02513-yen_US
dc.identifier.scopus2-s2.0-85135460318en_US
dc.institutionauthorN/A
dc.relation.publicationcategoryMakale - Uluslararası Hakemli Dergi - Kurum Öğretim Elemanıen_US
dc.authorwosidDiner, Öznur Yaşar/AAT-7443-2020
dc.khas20231019-WoSen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record