dc.contributor.author | Lochet, William | |
dc.contributor.author | Eiben, Eduard | |
dc.date.accessioned | 2021-06-14T07:50:12Z | |
dc.date.available | 2021-06-14T07:50:12Z | |
dc.date.created | 2021-02-07T14:59:44Z | |
dc.date.issued | 2020 | |
dc.identifier.issn | 1868-8969 | |
dc.identifier.uri | https://hdl.handle.net/11250/2759174 | |
dc.description.abstract | The line graph of a graph G is the graph L(G) whose vertex set is the edge set of G and there is an edge between e,f ∈ E(G) if e and f share an endpoint in G. A graph is called line graph if it is a line graph of some graph. We study the Line-Graph-Edge Deletion problem, which asks whether we can delete at most k edges from the input graph G such that the resulting graph is a line graph. More precisely, we give a polynomial kernel for Line-Graph-Edge Deletion with O(k⁵) vertices. This answers an open question posed by Falk Hüffner at Workshop on Kernels (WorKer) in 2013. | en_US |
dc.language.iso | eng | en_US |
dc.publisher | Schloss Dagstuhl, Leibniz-Zentrum für Informatik | en_US |
dc.rights | Navngivelse 4.0 Internasjonal | * |
dc.rights.uri | http://creativecommons.org/licenses/by/4.0/deed.no | * |
dc.title | A Polynomial Kernel for Line Graph Deletion | en_US |
dc.type | Journal article | en_US |
dc.type | Peer reviewed | en_US |
dc.description.version | publishedVersion | en_US |
dc.rights.holder | Copyright Eduard Eiben and William Loche | en_US |
dc.source.articlenumber | 42 | en_US |
cristin.ispublished | true | |
cristin.fulltext | original | |
cristin.qualitycode | 1 | |
dc.identifier.doi | 10.4230/LIPIcs.ESA.2020.42 | |
dc.identifier.cristin | 1887422 | |
dc.source.journal | Leibniz International Proceedings in Informatics | en_US |
dc.source.pagenumber | 1-15 | en_US |
dc.identifier.citation | Leibniz International Proceedings in Informatics. 2020, 173, 1-15, 42. | en_US |
dc.source.volume | 173 | en_US |