dc.contributor.author | Golovach, Petr | |
dc.contributor.author | Thilikos, Dimitrios | |
dc.contributor.author | Stamoulis, Giannos | |
dc.date.accessioned | 2021-05-19T11:11:29Z | |
dc.date.available | 2021-05-19T11:11:29Z | |
dc.date.created | 2021-01-04T13:27:53Z | |
dc.date.issued | 2020 | |
dc.Published | Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms. 2020, 931-950. | |
dc.identifier.issn | 1071-9040 | |
dc.identifier.uri | https://hdl.handle.net/11250/2755661 | |
dc.description.abstract | For a finite collection of graphs F, the F-TM-Deletion problem has as input an n-vertex graph G and an integer k and asks whether there exists a set S ⊆ V(G) with |S| ≤ k such that G \ S does not contain any of the graphs in F as a topological minor. We prove that for every such F, F-TM-Deletion is fixed parameter tractable on planar graphs. In particular, we provide an f(h, k) · n2 algorithm where h is an upper bound to the vertices of the graphs in F. | en_US |
dc.language.iso | eng | en_US |
dc.publisher | SIAM | en_US |
dc.rights | Navngivelse 4.0 Internasjonal | * |
dc.rights.uri | http://creativecommons.org/licenses/by/4.0/deed.no | * |
dc.title | Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable | en_US |
dc.type | Journal article | en_US |
dc.type | Peer reviewed | en_US |
dc.description.version | publishedVersion | en_US |
dc.rights.holder | Copyright 2020 SIAM | en_US |
cristin.ispublished | true | |
cristin.fulltext | postprint | |
cristin.qualitycode | 1 | |
dc.identifier.cristin | 1864820 | |
dc.source.journal | Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms | en_US |
dc.source.pagenumber | 931-950 | en_US |
dc.relation.project | Norges forskningsråd: 263317 | en_US |
dc.identifier.citation | Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms. 2020, 931–950 | en_US |