Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(3)
Connected Dominating Set
nphard problem
Planar Graph
Subscribe
Academic
Publications
Computational Study for Planar Connected Dominating Set Problem
Computational Study for Planar Connected Dominating Set Problem,10.1007/9783642174612_9,Marjan Marzban,QianPing Gu,Xiaohua Jia
Edit
Computational Study for Planar Connected Dominating Set Problem
BibTex

RIS

RefWorks
Download
Marjan Marzban
,
QianPing Gu
,
Xiaohua Jia
The
connected dominating set
(CDS) problem is a well studied
NPhard problem
with many important applications. Dorn et al. [ESA2005, LNCS3669,pp95106] introduce a new technique to generate 2O(Ö</font >n)2^{O(\sqrt{n})} time and fixedparameter algorithms for a number of nonlocal hard problems, including the CDS problem in planar graphs. The practical performance of this algorithm is yet to be evaluated. We perform a computational study for such an evaluation. The results show that the size of instances can be solved by the algorithm mainly depends on the branchwidth of the instances, coinciding with the theoretical result. For graphs with small or moderate branchwidth, the CDS problem instances with size up to a few thousands edges can be solved in a practical time and memory space. This suggests that the branchdecomposition based algorithms can be practical for the planar CDS problem.
Conference:
Conference on Combinatorial Optimization and Applications  COCOA
, pp. 107116, 2010
DOI:
10.1007/9783642174612_9
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
www.springerlink.com
)
(
www.springerlink.com
)
(
www.informatik.unitrier.de
)
(
dx.doi.org
)
(
adsabs.harvard.edu
)
More »
References
(23)
Computing Branch Decomposition of Large Planar Graphs
(
Citations: 3
)
Zhengbing Bian
,
Qianping Gu
Conference:
Workshop on Experimental and Efficient Algorithms  WEA
, pp. 87100, 2008
Connected Dominating Set in Sensor Networks and MANETs
(
Citations: 51
)
Jeremy Blum
,
Min Ding
,
Andrew Thaeler
,
Xiuzhen Cheng
Virtual backbone construction in multihop ad hoc wireless networks
(
Citations: 30
)
Xiuzhen Cheng
,
Min Ding
,
David Hongwei Du
,
Xiaohua Jia
Journal:
Wireless Communications and Mobile Computing
, vol. 6, no. 2, pp. 183190, 2006
Bidimensionality: new connections between FPT algorithms and PTASs
(
Citations: 57
)
Erik D. Demaine
,
MohammadTaghi Hajiaghayi
Conference:
ACMSIAM Symposium on Discrete Algorithms  SODA
, pp. 590601, 2005
Dynamic Programming and Fast Matrix Multiplication
(
Citations: 19
)
Frederic Dorn
Conference:
European Symposium on Algorithms  ESA
, pp. 280291, 2006