Search results for "Dominating set problem"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
2	Shai Gutner	Polynomial Kernels and Faster Algorithms for the Dominating Set Problem on Graphs with an Excluded Minor.	IWPEC	2009	DBLP DOI BibTeX RDF	H-minor-free graphs, degenerated graphs, dominating set problem, fixed-parameter tractable algorithms, problem kernel
2	Noga Alon, Shai Gutner	Linear Time Algorithms for Finding a Dominating Set of Fixed Size in Degenerated Graphs.	Algorithmica	2009	DBLP DOI BibTeX RDF	H-minor-free graphs, Degenerated graphs, Dominating set problem, Finding an induced cycle, Fixed-parameter tractable algorithms
2	Weiping Shang, F. Frances Yao, Peng-Jun Wan, Xiaodong Hu	On minimum m -connected k -dominating set problem in unit disc graphs.	J. Comb. Optim.	2008	DBLP DOI BibTeX RDF	k-dominating set, m-connectivity, Unit disc graph, Wireless sensor networks, Approximation algorithm
2	Marjan Marzban, Qian-Ping Gu, Xiaohua Jia	Computational Study on Dominating Set Problem of Planar Graphs.	COCOA	2008	DBLP DOI BibTeX RDF	PLANAR DOMINATING SET, computational study, data reduction, fixed-parameter algorithms, branch-decomposition
2	Weiping Shang, F. Frances Yao, Peng-Jun Wan, Xiaodong Hu	Algorithms for Minimum m -Connected k -Dominating Set Problem.	COCOA	2007	DBLP DOI BibTeX RDF	k-vertex connectivity, wireless sensor networks, approximation algorithm, Connected dominating set
2	Noga Alon, Shai Gutner	Linear Time Algorithms for Finding a Dominating Set of Fixed Size in Degenerated Graphs.	COCOON	2007	DBLP DOI BibTeX RDF	H-minor-free graphs, degenerated graphs, dominating set problem, finding an induced cycle, fixed-parameter tractable algorithms
2	Serge Gaspers, Dieter Kratsch, Mathieu Liedloff	Exponential Time Algorithms for the Minimum Dominating Set Problem on Some Graph Classes.	SWAT	2006	DBLP DOI BibTeX RDF
2	Takuro Fukunaga, Hiroshi Nagamochi	Approximation Algorithms for the b-Edge Dominating Set Problem and Its Related Problems.	COCOON	2005	DBLP DOI BibTeX RDF
2	Tim Nieberg, Johann Hurink	A PTAS for the Minimum Dominating Set Problem in Unit Disk Graphs.	WAOA	2005	DBLP DOI BibTeX RDF
2	Laura A. Sanchis	Experimental Analysis of Heuristic Algorithms for the Dominating Set Problem.	Algorithmica	2002	DBLP DOI BibTeX RDF	Approximation algorithms, Dominating set, Test cases
2	John A. Ellis, Hongbing Fan, Michael R. Fellows	The Dominating Set Problem Is Fixed Parameter Tractable for Graphs of Bounded Genus.	SWAT	2002	DBLP DOI BibTeX RDF	graph, dominating set, fixed parameter algorithm, genus
2	Robert D. Carr, Toshihiro Fujito, Goran Konjevod, Ojas Parekh	A 2 1/10-Approximation Algorithm for a Generalization of the Weighted Edge-Dominating Set Problem.	ESA	2000	DBLP DOI BibTeX RDF
2	Sun-Yuan Hsieh, Gen-Huey Chen, Chin-Wen Ho	An Optimal Parallel Algorithm for the Perfect Dominating Set Problem on Distance-Hereditary Graphs.	ASIAN	1998	DBLP DOI BibTeX RDF
1	Xu Zhu, Wei Wang 0032, Shan Shan, Zhong Wang, Weili Wu	A PTAS for the minimum weighted dominating set problem with smooth weights on unit disk graphs.	J. Comb. Optim.	2012	DBLP DOI BibTeX RDF
1	Wenkai Ma, Deying Li, Zhao Zhang	Algorithms for the minimum weight k-fold (connected) dominating set problem.	J. Comb. Optim.	2012	DBLP DOI BibTeX RDF
1	Chunmei Liu, Yinglei Song	Parameterized complexity and inapproximability of dominating set problem in chordal and near chordal graphs.	J. Comb. Optim.	2011	DBLP DOI BibTeX RDF
1	Luidi Simonetti, Alexandre Salles da Cunha, Abilio Lucena	The Minimum Connected Dominating Set Problem: Formulation, Valid Inequalities and a Branch-and-Cut Algorithm.	INOC	2011	DBLP DOI BibTeX RDF
1	Mingyu Xiao, Ton Kloks, Sheung-Hung Poon	New Parameterized Algorithms for the Edge Dominating Set Problem.	MFCS	2011	DBLP DOI BibTeX RDF
1	Anupama Potluri, Alok Singh	Two Hybrid Meta-heuristic Approaches for Minimum Dominating Set Problem.	SEMCCO	2011	DBLP DOI BibTeX RDF
1	Silvia M. Bianchi, Graciela L. Nasini, P. Tolomei	The set covering problem on circulant matrices: polynomial instances and the relation with the dominating set problem on webs.	Electronic Notes in Discrete Mathematics	2010	DBLP DOI BibTeX RDF
1	Vadim V. Lozin	A decidability result for the dominating set problem.	Theor. Comput. Sci.	2010	DBLP DOI BibTeX RDF
1	Xu Zhou, Guangxue Yue, ZhiBang Yang, Kenli Li	A New Approach for the Dominating-Set Problem by DNA-Based Supercomputing.	JSW	2010	DBLP DOI BibTeX RDF
1	Naoyuki Kamiyama	The Prize-Collecting Edge Dominating Set Problem in Trees.	MFCS	2010	DBLP DOI BibTeX RDF
1	Marjan Marzban, Qian-Ping Gu, Xiaohua Jia	Computational Study for Planar Connected Dominating Set Problem.	COCOA	2010	DBLP DOI BibTeX RDF
1	Abdel-Rahman Hedar, Rashad Ismail	Hybrid Genetic Algorithm for Minimum Dominating Set Problem.	ICCSA	2010	DBLP DOI BibTeX RDF
1	Chunmei Liu, Yinglei Song	Parameterized dominating set problem in chordal graphs: complexity and lower bound.	J. Comb. Optim.	2009	DBLP DOI BibTeX RDF
1	Marjan Marzban, Qian-Ping Gu, Xiaohua Jia	Computational study on planar dominating set problem.	Theor. Comput. Sci.	2009	DBLP DOI BibTeX RDF
1	Serge Gaspers, Dieter Kratsch, Mathieu Liedloff, Ioan Todinca	Exponential time algorithms for the minimum dominating set problem on some graph classes.	ACM Transactions on Algorithms	2009	DBLP DOI BibTeX RDF
1	Thomas Erlebach, Matús Mihalák	A (4 + epsilon)-Approximation for the Minimum-Weight Dominating Set Problem in Unit Disk Graphs.	WAOA	2009	DBLP DOI BibTeX RDF
1	Saeed Safaei, Babak Dalvand, Babak Esmaeili, Vahid Safaei	Molecular Solutions for the Minimum Edge Dominating Set Problem on DNA-based Supercomputing.	FCS	2009	DBLP BibTeX RDF
1	Junmin Zhu	Approximation for minimum total dominating set.	Int. Conf. Interaction Sciences	2009	DBLP DOI BibTeX RDF	minimum total dominating set, approximation, reduction
1	Xianyue Li, XiaoHua Xu, Feng Zou, Hongwei Du, Peng-Jun Wan, Yuexuan Wang, Weili Wu	A PTAS for Node-Weighted Steiner Tree in Unit Disk Graphs.	COCOA	2009	DBLP DOI BibTeX RDF	Node-weighted Steiner tree, minimum weighted connected dominating set, approximation algorithm, polynomial-time approximation scheme
1	Geevarghese Philip, Venkatesh Raman, Somnath Sikdar	Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels.	ESA	2009	DBLP DOI BibTeX RDF
1	Jianxin Wang, Beiwei Chen, Qilong Feng, Jianer Chen	An Efficient Fixed-Parameter Enumeration Algorithm for Weighted Edge Dominating Set.	FAW	2009	DBLP DOI BibTeX RDF
1	Hans L. Bodlaender, Daniel Lokshtanov, Eelko Penninkx	Planar Capacitated Dominating Set Is W[1]-Hard.	IWPEC	2009	DBLP DOI BibTeX RDF
1	Henning Fernau, Joachim Kneis, Dieter Kratsch, Alexander Langer, Mathieu Liedloff, Daniel Raible, Peter Rossmanith	An Exact Algorithm for the Maximum Leaf Spanning Tree Problem.	IWPEC	2009	DBLP DOI BibTeX RDF
1	Christoph Böhm, Philip Groth, Ulf Leser	Graph-Based Ontology Construction from Heterogenous Evidences.	International Semantic Web Conference	2009	DBLP DOI BibTeX RDF
1	Jianer Chen, Iyad A. Kanj, Ge Xia	On Parameterized Exponential Time Complexity.	TAMC	2009	DBLP DOI BibTeX RDF
1	Daniel Lokshtanov, Matthias Mnich, Saket Saurabh	Linear Kernel for Planar Connected Dominating Set.	TAMC	2009	DBLP DOI BibTeX RDF
1	Erik D. Demaine, MohammadTaghi Hajiaghayi, Ken-ichi Kawarabayashi	Algorithmic Graph Minor Theory: Improved Grid Minor Bounds and Wagner's Contraction.	Algorithmica	2009	DBLP DOI BibTeX RDF	Bidimensionality, Wagner’s conjecture, Graph algorithms, Treewidth, Graph minors, Grid graphs
1	Noga Alon, Shai Gutner	Kernels for the Dominating Set Problem on Graphs with an Excluded Minor.	Electronic Colloquium on Computational Complexity (ECCC)	2008	DBLP BibTeX RDF
1	Beat Gfeller, Elias Vicari	A Faster Distributed Approximation Scheme for the Connected Dominating Set Problem for Growth-Bounded Graphs.	Ad Hoc & Sensor Wireless Networks	2008	DBLP BibTeX RDF
1	Tetz C. Huang, Chih-Yuan Chen, Cheng-Pin Wang	A Linear-Time Self-Stabilizing Algorithm for the Minimal 2-Dominating Set Problem in General Networks.	J. Inf. Sci. Eng.	2008	DBLP BibTeX RDF
1	Himanshu Gupta, Vishnu Navda, Samir R. Das, Vishal Chowdhary	Efficient gathering of correlated data in sensor networks.	TOSN	2008	DBLP DOI BibTeX RDF	Correlated Data, Energy Efficiency, Topology Control
1	Ding-Zhu Du	Double Partition: (6+epsilon)-Approximation for Minimum Weight Dominating Set in Unit Disk Graphs.	AAIM	2008	DBLP DOI BibTeX RDF
1	Venkatesh Raman, Saket Saurabh, Sriganesh Srihari	Parameterized Algorithms for Generalized Domination.	COCOA	2008	DBLP DOI BibTeX RDF
1	Daniel Raible, Henning Fernau	Power Domination in O*(1.7548n) Using Reference Search Trees.	ISAAC	2008	DBLP DOI BibTeX RDF
1	Johan M. M. van Rooij, Hans L. Bodlaender	Exact Algorithms for Edge Domination.	IWPEC	2008	DBLP DOI BibTeX RDF	minimum maximal matching, exponential time algorithms, measure and conquer, exact algorithms, edge dominating set
1	Thomas Erlebach, Erik Jan van Leeuwen	Domination in Geometric Intersection Graphs.	LATIN	2008	DBLP DOI BibTeX RDF
1	André Berger, Ojas Parekh	Linear Time Algorithms for Generalized Edge Dominating Set Problems.	Algorithmica	2008	DBLP DOI BibTeX RDF	Approximation algorithm, Trees, Edge dominating set
1	Fedor V. Fomin, Fabrizio Grandoni, Dieter Kratsch	Solving Connected Dominating Set Faster than 2 n .	Algorithmica	2008	DBLP DOI BibTeX RDF	Exponential-time exact algorithm, Maximum leaf spanning tree, Connected dominating set, NP-hard problem
1	Jiong Guo, Rolf Niedermeier, Daniel Raible	Improved Algorithms and Complexity Results for Power Domination in Graphs.	Algorithmica	2008	DBLP DOI BibTeX RDF	Graphs of bounded treewidth, (Power) domination in graphs, Computational complexity, Graph algorithms, Parameterized complexity, Design and analysis of algorithms, Fixed-parameter algorithms
1	Venkatesh Raman, Saket Saurabh	Short Cycles Make W -hard Problems Hard: FPT Algorithms for W -hard Problems in Graphs with no Short Cycles.	Algorithmica	2008	DBLP DOI BibTeX RDF	t-vertex cover, Dominating set, Set cover, Independent set, Parameterized complexity
1	Weiping Shang, Peng-Jun Wan, F. Frances Yao, Xiaodong Hu	Algorithms for minimum m-connected k-tuple dominating set problem.	Theor. Comput. Sci.	2007	DBLP DOI BibTeX RDF
1	André Berger, Takuro Fukunaga, Hiroshi Nagamochi, Ojas Parekh	Approximability of the capacitated b-edge dominating set problem.	Theor. Comput. Sci.	2007	DBLP DOI BibTeX RDF
1	Beat Gfeller, Elias Vicari	A Faster Distributed Approximation Scheme for the Connected Dominating Set Problem for Growth-Bounded Graphs.	ADHOC-NOW	2007	DBLP DOI BibTeX RDF	Growth-Bounded Graphs, Distributed Approximation Scheme, Distributed Algorithms, Connected Dominating Set
1	Tong Yi, Guoli Ding, Bogdan Oporowski	A Low Bound for Broadcast in Optical Networks of Bounded Treewidth Using Fewest Converters.	IPCCC	2007	DBLP DOI BibTeX RDF
1	Carmen Martínez, Ramón Beivide, Ernst M. Gabidulin	Perfect Codes for Metrics Induced by Circulant Graphs.	IEEE Transactions on Information Theory	2007	DBLP DOI BibTeX RDF
1	Ashkan Aazami, Michael D. Stilp	Approximation Algorithms and Hardness for Domination with Propagation.	APPROX-RANDOM	2007	DBLP DOI BibTeX RDF	Power Dominating Set, Approximation Algorithms, Integer Programming, Planar Graphs, Greedy Algorithms, Dominating Set, Hardness of Approximation, PTAS
1	Ning Chen, Roee Engelberg, C. Thach Nguyen, Prasad Raghavendra, Atri Rudra, Gyanit Singh	Improved Approximation Algorithms for the Spanning Star Forest Problem.	APPROX-RANDOM	2007	DBLP DOI BibTeX RDF
1	Andrzej Czygrinow, Michal Hanckowiak	Distributed Approximation Algorithms for Weighted Problems in Minor-Closed Families.	COCOON	2007	DBLP DOI BibTeX RDF
1	Li Li, Bin Qin, Chunyuan Zhang, Haiyan Li	Efficient Broadcasting in Multi-radio Multi-channel and Multi-hop Wireless Networks Based on Self-pruning.	HPCC	2007	DBLP DOI BibTeX RDF
1	Li Li, Bin Qin, Chunyuan Zhang	Broadcasting in Multi-Radio Multi-Channel and Multi-Hop Wireless Networks.	MMNS	2007	DBLP DOI BibTeX RDF
1	Chin Kuan Ho, Yashwant Prasad Singh, Hong Tat Ewe	An Enhanced Ant Colony Optimization Metaheuristic for the Minimum Dominating Set Problem.	Applied Artificial Intelligence	2006	DBLP DOI BibTeX RDF
1	Jie Wu, Mihaela Cardei, Fei Dai, Shuhui Yang	Extended Dominating Set and Its Applications in Ad Hoc Networks Using Cooperative Communication.	IEEE Trans. Parallel Distrib. Syst.	2006	DBLP DOI BibTeX RDF	simulation, Ad hoc network, connectivity, dominating set, cooperative communication
1	Christoph Ambühl, Thomas Erlebach, Matús Mihalák, Marc Nunkesser	Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs.	APPROX-RANDOM	2006	DBLP DOI BibTeX RDF
1	Fedor V. Fomin, Fabrizio Grandoni, Dieter Kratsch	Solving Connected Dominating Set Faster Than 2n.	FSTTCS	2006	DBLP DOI BibTeX RDF
1	Erik D. Demaine, Mohammad Taghi Hajiaghayi, Ken-ichi Kawarabayashi	Algorithmic Graph Minor Theory: Improved Grid Minor Bounds and Wagner's Contraction.	ISAAC	2006	DBLP DOI BibTeX RDF
1	Chunmei Liu, Yinglei Song	Exact Algorithms for Finding the Minimum Independent Dominating Set in Graphs.	ISAAC	2006	DBLP DOI BibTeX RDF
1	Yijia Chen, Jörg Flum	The Parameterized Complexity of Maximality and Minimality Problems.	IWPEC	2006	DBLP DOI BibTeX RDF
1	Frederic Dorn, Jan Arne Telle	Two Birds with One Stone: The Best of Branchwidth and Treewidth with One Algorithm.	LATIN	2006	DBLP DOI BibTeX RDF
1	Frank K. H. A. Dehne, Michael R. Fellows, Henning Fernau, Elena Prieto, Frances A. Rosamond	NONBLOCKER: Parameterized Algorithmics for minimum dominating set.	SOFSEM	2006	DBLP DOI BibTeX RDF
1	Bin Fu	Theory and Application of Width Bounded Geometric Separator.	STACS	2006	DBLP DOI BibTeX RDF
1	Venkatesh Raman, Saket Saurabh	Triangles, 4-Cycles and Parameterized (In-)Tractability.	SWAT	2006	DBLP DOI BibTeX RDF
1	Andrzej Czygrinow, Michal Hanckowiak	Distributed Approximation Algorithms in Unit-Disk Graphs.	DISC	2006	DBLP DOI BibTeX RDF
1	Shin'ichi Wakabayashi, Kenji Kikuchi	Solving the Minimum Dominating Set Problem with Instance-Specific Hardware on FPGAs.	FPT	2005	DBLP BibTeX RDF
1	Fabian Kuhn, Tim Nieberg, Thomas Moscibroda, Roger Wattenhofer	Local approximation schemes for ad hoc and sensor networks.	DIALM-POMC	2005	DBLP DOI BibTeX RDF	distributed algorithm, approximation, wireless ad hoc networks, maximum independent set, minimum dominating set
1	Himanshu Gupta, Vishnu Navda, Samir R. Das, Vishal Chowdhary	Efficient gathering of correlated data in sensor networks.	MobiHoc	2005	DBLP DOI BibTeX RDF	correlated data, energy efficiency, topology control
1	Jiong Guo, Rolf Niedermeier, Daniel Raible	Improved Algorithms and Complexity Results for Power Domination in Graphs.	FCT	2005	DBLP DOI BibTeX RDF
1	Fedor V. Fomin, Fabrizio Grandoni, Artem V. Pyatkin, Alexey A. Stepanov	Bounding the Number of Minimal Dominating Sets: A Measure and Conquer Approach.	ISAAC	2005	DBLP DOI BibTeX RDF
1	Pinar Heggernes, Daniel Lokshtanov	Optimal Broadcast Domination of Arbitrary Graphs in Polynomial Time.	WG	2005	DBLP DOI BibTeX RDF
1	Erik D. Demaine, Mohammad Taghi Hajiaghayi, Dimitrios M. Thilikos	Exponential Speedup of Fixed-Parameter Algorithms for Classes of Graphs Excluding Single-Crossing Graphs as Minors.	Algorithmica	2005	DBLP DOI BibTeX RDF	Subexponential algorithms, Dominating set, Graph minors
1	Ya-feng Wu, Yinlong Xu, Guo-Liang Chen	Approximation Algorithms for Steiner Connected Dominating Set.	J. Comput. Sci. Technol.	2005	DBLP DOI BibTeX RDF	Steiner connected dominated set, approximation algorithm, graph algorithm, NP-hard
1	Christiaan V. Henkel, Reno S. Bladergroen, Crina I. A. Balog, André M. Deelder, Tom Head, Grzegorz Rozenberg, Herman P. Spaink	Protein output for DNA computing.	Natural Computing	2005	DBLP DOI BibTeX RDF	plasmid computing, DNA computing, proteomics
1	Ning Chen, Jie Meng, Jiawei Rong, Hong Zhu	Approximation for Dominating Set Problem with Measure Functions.	Computers and Artificial Intelligence	2004	DBLP BibTeX RDF
1	Vladimir E. Alekseev, Dmitry V. Korobitsyn, Vadim V. Lozin	Boundary classes of graphs for the dominating set problem.	Discrete Mathematics	2004	DBLP DOI BibTeX RDF
1	Minyi Guo, Michael (Shan-Hui) Ho, Weng-Long Chang	Fast parallel molecular solution to the dominating-set problem on massively parallel bio-computing.	Parallel Computing	2004	DBLP DOI BibTeX RDF
1	John A. Ellis, Hongbing Fan, Michael R. Fellows	The dominating set problem is fixed parameter tractable for graphs of bounded genus.	J. Algorithms	2004	DBLP DOI BibTeX RDF
1	Fedor V. Fomin, Dieter Kratsch, Gerhard J. Woeginger	Exact (Exponential) Algorithms for the Dominating Set Problem.	WG	2004	DBLP DOI BibTeX RDF
1	Stephen Eubank, V. S. Anil Kumar, Madhav V. Marathe, Aravind Srinivasan, Nan Wang	Structural and algorithmic aspects of massive social networks.	SODA	2004	DBLP DOI BibTeX RDF
1	Jochen Alber, Michael R. Fellows, Rolf Niedermeier	Polynomial-time data reduction for dominating set.	J. ACM	2004	DBLP DOI BibTeX RDF	plannar graphs, problem kernel, NP-complete problems, dominating set, data reduction, fixed-parameter tractability
1	Biing-Feng Wang	Finding r-Dominating Sets and p-Centers of Trees in Parallel.	IEEE Trans. Parallel Distrib. Syst.	2004	DBLP DOI BibTeX RDF
1	Miroslav Chlebík, Janka Chlebíková	Approximation Hardness of Dominating Set Problems.	ESA	2004	DBLP DOI BibTeX RDF
1	Fedor V. Fomin, Dimitrios M. Thilikos	Fast Parameterized Algorithms for Graphs on Surfaces: Linear Kernel and Exponential Speed-Up.	ICALP	2004	DBLP DOI BibTeX RDF	embedded graphs, subexponential algorithms, Dominating set, parameterized algorithms, branch-width
1	Yijia Chen, Jörg Flum	On Miniaturized Problems in Parameterized Complexity Theory.	IWPEC	2004	DBLP DOI BibTeX RDF
1	Igor E. Zverovich	A Characterization of Domination Reducible Graphs.	Graphs and Combinatorics	2004	DBLP DOI BibTeX RDF	Domination number, Hereditary class of graphs, Forbidden induced subgraph, Homogeneous set
1	Elena Prieto, Christian Sloper	Either/Or: Using Vertex Cover Structure in Designing FPT-Algorithms - The Case of k-Internal Spanning Tree.	WADS	2003	DBLP DOI BibTeX RDF
1	Toshihiro Fujito, Hiroshi Nagamochi	A 2-approximation algorithm for the minimum weight edge dominating set problem.	Discrete Applied Mathematics	2002	DBLP DOI BibTeX RDF
1	Ojas Parekh	Edge dominating and hypomatchable sets.	SODA	2002	DBLP DOI BibTeX RDF
1	Tzu-Chin Lin, Biing-Feng Wang	Efficient Parallel Algorithms for the r-Dominating Set and p-Center Problems on Trees.	ICPADS	2002	DBLP DOI BibTeX RDF