Skip to main content

Research Repository

Advanced Search

Detecting induced star-like minors in polynomial time

Fiala, J.; Kaminksi, M.; Paulusma, D.

Detecting induced star-like minors in polynomial time Thumbnail


Authors

J. Fiala

M. Kaminksi



Abstract

The Induced Minor problem is to test whether a graph G contains a graph H as an induced minor, i.e., if G can be modified into H by a sequence of vertex deletions and edge contractions. When H is fixed, i.e., not part of the input, this problem is denoted H-Induced Minor. We provide polynomial-time algorithms for this problem in the case that the fixed target graph has a star-like structure. In particular, we show polynomial-time solvability for all forests H on at most seven vertices except for one such case.

Citation

Fiala, J., Kaminksi, M., & Paulusma, D. (2012). Detecting induced star-like minors in polynomial time. Journal of discrete algorithms, 17, 74-85. https://doi.org/10.1016/j.jda.2012.11.002

Journal Article Type Article
Publication Date Dec 1, 2012
Deposit Date Mar 11, 2013
Publicly Available Date Mar 28, 2024
Journal Journal of Discrete Algorithms
Print ISSN 1570-8667
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 17
Pages 74-85
DOI https://doi.org/10.1016/j.jda.2012.11.002
Keywords Induced minor, Tree, Computational complexity.
Public URL https://durham-repository.worktribe.com/output/1495906

Files

Accepted Journal Article (383 Kb)
PDF

Copyright Statement
NOTICE: this is the author’s version of a work that was accepted for publication in Journal of discrete algorithms. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Journal of discrete algorithms, 12, 2012, 10.1016/j.jda.2012.11.002





You might also like



Downloadable Citations