Leaf sector covers with applications on circle graphs

Abstract

Damian and Pemmaraju (2002) [8] introduced leaf sector covers for circle graphs and presented an O ( n 2 )-time algorithm to find this data structure. They subsequently employed it as an algorithmic tool, leading to the development of an 8 -approximation algorithm for the dominating set problem, a (2 + e ) -approximation scheme for the dominating set problem, and a (3 + e ) - approximation scheme for the total dominating set problem. In this paper, we have improved the time complexity from O ( n 2 ) to O ( n + m ) for finding a leaf sector cover. Furthermore, we employed leaf sector covers as a powerful algorithmic tool to design a 10 -approximation algorithm for the total dominating set problem and a 12approximation algorithm for the paired -dominating set problem. Moreover, we also proposed a (2 + e ) -approximation scheme for the total dominating set problem and a (4 + e ) -approximation scheme for the paired -dominating set problem. The results presented above are currently the best algorithms for circle graphs.