TY - GEN
T1 - Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
AU - Alon, Noga
AU - Gutner, Shai
PY - 2007
Y1 - 2007
N2 - There is substantial literature dealing with fixed parameter algorithms for the dominating set problem on various families of graphs. In this paper, we give a kO(dk)n time algorithm for finding a dominating set of size at most k in a d-degenerated graph with n vertices. This proves that the dominating set problem is fixed-parameter tractable for degenerated graphs. For graphs that do not contain Kh as a topological minor, we give an improved algorithm for the problem with running time (O(h))hkn. For graphs which are Kh-minor-free, the running time is further reduced to (O(log h))hk/2n. Fixed-parameter tractable algorithms that are linear in the number of vertices of the graph were previously known only for planar graphs. For the families of graphs discussed above, the problem of finding an induced cycle of a given length is also addressed. For every fixed H and k, we show that if an H-minor-free graph G with n vertices contains an induced cycle of size k, then such a cycle can be found in O(n) expected time as well as in O(n log n) worst-case time. Some results are stated concerning the (im)possibility of establishing linear time algorithms for the more general family of degenerated graphs.
AB - There is substantial literature dealing with fixed parameter algorithms for the dominating set problem on various families of graphs. In this paper, we give a kO(dk)n time algorithm for finding a dominating set of size at most k in a d-degenerated graph with n vertices. This proves that the dominating set problem is fixed-parameter tractable for degenerated graphs. For graphs that do not contain Kh as a topological minor, we give an improved algorithm for the problem with running time (O(h))hkn. For graphs which are Kh-minor-free, the running time is further reduced to (O(log h))hk/2n. Fixed-parameter tractable algorithms that are linear in the number of vertices of the graph were previously known only for planar graphs. For the families of graphs discussed above, the problem of finding an induced cycle of a given length is also addressed. For every fixed H and k, we show that if an H-minor-free graph G with n vertices contains an induced cycle of size k, then such a cycle can be found in O(n) expected time as well as in O(n log n) worst-case time. Some results are stated concerning the (im)possibility of establishing linear time algorithms for the more general family of degenerated graphs.
KW - Degenerated graphs
KW - Dominating set problem
KW - Finding an induced cycle
KW - Fixed-parameter tractable algorithms
KW - H-minor-free graphs
UR - http://www.scopus.com/inward/record.url?scp=37849019999&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=37849019999&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:37849019999
SN - 9783540735441
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 394
EP - 405
BT - Computing and Combinatorics - 13th Annual International Conference, COCOON 2007, Proceedings
T2 - 13th Annual International Computing and Combinatorics Conference, COCOON 2007
Y2 - 16 July 2007 through 19 July 2007
ER -