Show simple item record

dc.contributor.authorCrespelle, Christophe Dominique
dc.contributor.authorFeghali, Carl
dc.contributor.authorGolovach, Petr
dc.PublishedCrespelle CD, Feghali C, Golovach P. Cyclability in Graph Classes. Leibniz International Proceedings in Informatics. 2019;149:16:1-16:13eng
dc.description.abstractA subset T subseteq V(G) of vertices of a graph G is said to be cyclable if G has a cycle C containing every vertex of T, and for a positive integer k, a graph G is k-cyclable if every subset of vertices of G of size at most k is cyclable. The Terminal Cyclability problem asks, given a graph G and a set T of vertices, whether T is cyclable, and the k-Cyclability problem asks, given a graph G and a positive integer k, whether G is k-cyclable. These problems are generalizations of the classical Hamiltonian Cycle problem. We initiate the study of these problems for graph classes that admit polynomial algorithms for Hamiltonian Cycle. We show that Terminal Cyclability can be solved in linear time for interval graphs, bipartite permutation graphs and cographs. Moreover, we construct certifying algorithms that either produce a solution, that is, a cycle, or output a graph separator that certifies a no-answer. We use these results to show that k-Cyclability can be solved in polynomial time when restricted to the aforementioned graph classes.en_US
dc.publisherDagstuhl Publishingen_US
dc.rightsAttribution CC BYeng
dc.titleCyclability in Graph Classesen_US
dc.typePeer reviewed
dc.typeJournal article
dc.rights.holderCopyright 2019 The Author(s)en_US
dc.source.journalLeibniz International Proceedings in Informatics
dc.relation.projectNorges forskningsråd: 249994
dc.relation.projectNorges forskningsråd: 263317

Files in this item


This item appears in the following Collection(s)

Show simple item record

Attribution CC BY
Except where otherwise noted, this item's license is described as Attribution CC BY