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

Institution:	^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 等数据库收录！