A Polynomial Kernel for 3-Leaf Power Deletion
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Jungho Ahn | - |
dc.contributor.author | Eiben, Eduard | - |
dc.contributor.author | O. -Joung Kwon | - |
dc.contributor.author | Sang-Il Oum | - |
dc.date.accessioned | 2023-10-30T22:01:01Z | - |
dc.date.available | 2023-10-30T22:01:01Z | - |
dc.date.created | 2023-05-30 | - |
dc.date.issued | 2023-10 | - |
dc.identifier.issn | 0178-4617 | - |
dc.identifier.uri | https://pr.ibs.re.kr/handle/8788114/14057 | - |
dc.description.abstract | For a non-negative integer t, the t-leaf power of a tree T is a simple graph G on the leaves of T such that two vertices are adjacent in G if and only if their distance in T is at most t. We provide a polynomial kernel for the problem of deciding whether we can delete at most k vertices to make an input graph a 3-leaf power of some tree. More specifically, we present a polynomial-time algorithm for an input instance (G, k) for the problem to output an equivalent instance (G', k') such that k'= k and G' has at most O(k14) vertices. | - |
dc.language | 영어 | - |
dc.publisher | SPRINGER | - |
dc.title | A Polynomial Kernel for 3-Leaf Power Deletion | - |
dc.type | Article | - |
dc.type.rims | ART | - |
dc.identifier.wosid | 000985432100001 | - |
dc.identifier.scopusid | 2-s2.0-85158937891 | - |
dc.identifier.rimsid | 80879 | - |
dc.contributor.affiliatedAuthor | Jungho Ahn | - |
dc.contributor.affiliatedAuthor | O. -Joung Kwon | - |
dc.contributor.affiliatedAuthor | Sang-Il Oum | - |
dc.identifier.doi | 10.1007/s00453-023-01129-9 | - |
dc.identifier.bibliographicCitation | ALGORITHMICA, v.85, no.10, pp.3058 - 3087 | - |
dc.relation.isPartOf | ALGORITHMICA | - |
dc.citation.title | ALGORITHMICA | - |
dc.citation.volume | 85 | - |
dc.citation.number | 10 | - |
dc.citation.startPage | 3058 | - |
dc.citation.endPage | 3087 | - |
dc.type.docType | Article | - |
dc.description.journalClass | 1 | - |
dc.description.journalClass | 1 | - |
dc.description.isOpenAccess | N | - |
dc.description.journalRegisteredClass | scie | - |
dc.description.journalRegisteredClass | scopus | - |
dc.relation.journalResearchArea | Computer Science | - |
dc.relation.journalResearchArea | Mathematics | - |
dc.relation.journalWebOfScienceCategory | Computer Science, Software Engineering | - |
dc.relation.journalWebOfScienceCategory | Mathematics, Applied | - |
dc.subject.keywordPlus | VERTEX | - |
dc.subject.keywordPlus | ALGORITHM | - |
dc.subject.keywordPlus | GRAPHS | - |
dc.subject.keywordAuthor | l-Leaf power | - |
dc.subject.keywordAuthor | Parameterized | - |
dc.subject.keywordAuthor | Algorithm | - |
dc.subject.keywordAuthor | Kernelization | - |
dc.subject.keywordAuthor | Vertex deletion | - |