The dominating set problem is fixed parameter tractable for graphs of bounded genus期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

The dominating set problem is fixed parameter tractable for graphs of bounded genus

Authors:	J Ellis H Fan M Fellows

Affiliation:	^aDepartment of Physics and Computer Science, Wilfrid Laurier University, Waterloo, Ontario, N2L 305, Canada;^bDepartment of Computer Science, University of Victoria, PO Box 3055, Victoria, British Columbia, V8W 3P6, Canada;^cDepartment of Computer Science, University of Newcastle, Newcastle, New South Wales, Australia

Abstract:	We describe an algorithm for the dominating set problem with time complexity O((4g+40)^kn²) for graphs of bounded genus g1, where k is the size of the set. It has previously been shown that this problem is fixed parameter tractable for planar graphs. We give a simpler proof for the previous O(8^kn²) result for planar graphs. Our method is a refinement of the earlier techniques.

Keywords:	Graph Genus Dominating set Fixed parameter algorithm
本文献已被 ScienceDirect 等数据库收录！