Block Elimination Distance

dc.authorid Diner, Öznur Yaşar/0000-0002-9271-2691
dc.authorid Stamoulis, Giannos/0000-0002-4175-7793
dc.authorwosid Diner, Öznur Yaşar/AAT-7443-2020
dc.contributor.author Yaşar Diner, Öznur
dc.contributor.author Giannopoulou, Archontia C.
dc.contributor.author Stamoulis, Giannos
dc.contributor.author Thilikos, Dimitrios M.
dc.contributor.other Computer Engineering
dc.date.accessioned 2023-10-19T15:12:47Z
dc.date.available 2023-10-19T15:12:47Z
dc.date.issued 2022
dc.department-temp [Diner, Oznur Yasar] Kadir Has Univ, Comp Engn Dept, Istanbul, Turkey; [Diner, Oznur Yasar] Univ Politecn Cataluna, Dept Math, Barcelona, Spain; [Giannopoulou, Archontia C.; Stamoulis, Giannos] Natl & Kapodistrian Univ Athens, Dept Informat & Telecommun, Athens, Greece; [Stamoulis, Giannos; Thilikos, Dimitrios M.] Univ Montpellier, CNRS, LIRMM, Montpellier, France en_US
dc.description.abstract We 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 correct en_US
dc.description.sponsorship Spanish 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.sponsorship Oznur 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.identifier.citationcount 1
dc.identifier.doi 10.1007/s00373-022-02513-y en_US
dc.identifier.issn 0911-0119
dc.identifier.issn 1435-5914
dc.identifier.issue 5 en_US
dc.identifier.scopus 2-s2.0-85135460318 en_US
dc.identifier.scopusquality Q2
dc.identifier.uri https://doi.org/10.1007/s00373-022-02513-y
dc.identifier.uri https://hdl.handle.net/20.500.12469/5534
dc.identifier.volume 38 en_US
dc.identifier.wos WOS:000836615400002 en_US
dc.identifier.wosquality N/A
dc.khas 20231019-WoS en_US
dc.language.iso en en_US
dc.publisher Springer Japan Kk en_US
dc.relation.ispartof Graphs and Combinatorics en_US
dc.relation.publicationcategory Makale - Uluslararası Hakemli Dergi - Kurum Öğretim Elemanı en_US
dc.rights info:eu-repo/semantics/openAccess en_US
dc.scopus.citedbyCount 5
dc.subject Graph minors en_US
dc.subject Block elimination distance en_US
dc.subject Elimination distance en_US
dc.subject Minor obstructions en_US
dc.subject Parameterized algorithms en_US
dc.title Block Elimination Distance en_US
dc.type Article en_US
dc.wos.citedbyCount 5
dspace.entity.type Publication
relation.isAuthorOfPublication 84ac79d3-823a-4abf-9b15-e1383ec8a9f5
relation.isAuthorOfPublication.latestForDiscovery 84ac79d3-823a-4abf-9b15-e1383ec8a9f5
relation.isOrgUnitOfPublication fd8e65fe-c3b3-4435-9682-6cccb638779c
relation.isOrgUnitOfPublication.latestForDiscovery fd8e65fe-c3b3-4435-9682-6cccb638779c

Files

Original bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
5534.pdf
Size:
745.98 KB
Format:
Adobe Portable Document Format
Description:
Tam Metin / Full Text