Contracting to a longest path in H-free graphs
(2020)
Presentation / Conference Contribution
Kern, W., & Paulusma, D. (2020). Contracting to a longest path in H-free graphs. In Y. Cao, S. Cheng, & M. Li (Eds.), 31st International Symposium on Algorithms and Computation (ISAAC 2020) (22:1-22:18). https://doi.org/10.4230/lipics.isaac.2020.22
The Path Contraction problem has as input a graph G and an integer k and is to decide if G can be modified to the k-vertex path P_k by a sequence of edge contractions. A graph G is H-free for some graph H if G does not contain H as an induced subgrap... Read More about Contracting to a longest path in H-free graphs.