2019 •
Algorithms for deletion problems on split graphs
Authors:
Dekel Tsur
Abstract:
Abstract In the Split to Block Vertex Deletion and Split to Threshold Vertex Deletion problems the input is a split graph G and an integer k, and the goal is to decide whether there is a set S of vertices of size at most k such that G − S is a block graph and G − S is a threshold graph, respectively. In this paper we give algorithms for these problems whose running times are O ⁎ ( 2.076 k ) and O ⁎ ( 1.619 k ) , respectively.
We have placed cookies on your device to help make this website and the services we offer better. By using this site, you agree to the use of cookies. Learn more