Title :
Domination in bounded interval tolerance graphs
Author :
Adhar, Gur Saran
Author_Institution :
Dept. of Comput. Sci., North Carolina Univ., Wilmington, NC, USA
Abstract :
We present efficient algorithms for solving the domination set problem for the class of bounded tolerance graphs. The class of bounded tolerance graphs includes interval graphs and permutation graphs as sub-classes. Our solution to the domination set problem has improved bounds for time complexity compared to the algorithm for general co-comparability graphs which can also be used for bounded tolerance graphs
Keywords :
computational complexity; graph theory; set theory; bounded interval tolerance graphs; domination set problem; permutation graph; time complexity; Algorithm design and analysis; Computer science; NP-complete problem; Polynomials; Tree data structures; Very large scale integration;
Conference_Titel :
Parallel and Distributed Systems: Workshops, Seventh International Conference on, 2000
Conference_Location :
Iwate
Print_ISBN :
0-7695-0571-6
DOI :
10.1109/PADSW.2000.884511
