Search results for "minimum dominating set"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
2	Saurav Pandit, Sriram V. Pemmaraju	Rapid randomized pruning for fast greedy distributed algorithms.	PODC	2010	DBLP DOI BibTeX RDF	distributed algorithms, randomized algorithms, greedy algorithms, facility location, primal-dual algorithms, minimum dominating set
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	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
2	Tim Nieberg, Johann Hurink	A PTAS for the Minimum Dominating Set Problem in Unit Disk Graphs.	WAOA	2005	DBLP DOI BibTeX RDF
2	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	Anupama Potluri, Alok Singh	Two Hybrid Meta-heuristic Approaches for Minimum Dominating Set Problem.	SEMCCO	2011	DBLP DOI BibTeX RDF
1	Michael A. Henning, Christian Löwenstein, Dieter Rautenbach	An independent dominating set in the complement of a minimum dominating set of a tree.	Appl. Math. Lett.	2010	DBLP DOI BibTeX RDF
1	Henning Fernau	minimum dominating set of queens: A trivial programming exercise?	Discrete Applied Mathematics	2010	DBLP DOI BibTeX RDF
1	Chao Shen, Tao Li	Multi-Document Summarization via the Minimum Dominating Set.	COLING	2010	DBLP BibTeX RDF
1	Christoph Lenzen, Roger Wattenhofer	Minimum Dominating Set Approximation in Graphs of Bounded Arboricity.	DISC	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	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	Irina Astrovskaya, Alexander Zelikovsky	Genotype Tagging with Limited Overfitting.	BSB	2009	DBLP DOI BibTeX RDF	genotype tagging, linear programming, hypergraph, minimum dominating set
1	Fedor V. Fomin, Serge Gaspers, Saket Saurabh, Alexey A. Stepanov	On Two Techniques of Combining Branching and Treewidth.	Algorithmica	2009	DBLP DOI BibTeX RDF	Exact exponential time algorithms, #3-Coloring, #Minimum dominating set, Minimum maximal matching, k-Weighted vertex cover, NP hard problems, Treewidth, Parameterized algorithms
1	Khac Tiep Mai, Dongkun Shin, Hyunseung Choo	Connectivity-based clustering with stretching technique in MANETs.	ICUIMC	2009	DBLP DOI BibTeX RDF	k-hop dominating set, multi-hop clustering, stretching clustering, ad hoc networks, mobility, stability
1	Fedor V. Fomin, Fabrizio Grandoni, Dieter Kratsch	A measure & conquer approach for the analysis of exact algorithms.	J. ACM	2009	DBLP DOI BibTeX RDF	Dominating set, exact algorithm, independent set
1	Saurav Pandit, Sriram V. Pemmaraju, Kasturi R. Varadarajan	Approximation Algorithms for Domatic Partitions of Unit Disk Graphs.	APPROX-RANDOM	2009	DBLP DOI BibTeX RDF
1	Johan M. M. van Rooij, Jesper Nederlof, Thomas C. van Dijk	Inclusion/Exclusion Meets Measure and Conquer.	ESA	2009	DBLP DOI BibTeX RDF
1	Binh-Minh Bui-Xuan, Jan Arne Telle, Martin Vatshelle	Boolean-Width of Graphs.	IWPEC	2009	DBLP DOI BibTeX RDF
1	Michael R. Fellows, Daniel Lokshtanov, Neeldhara Misra, Matthias Mnich, Frances A. Rosamond, Saket Saurabh	The Complexity Ecology of Parameters: An Illustration Using Bounded Max Leaf Number.	Theory Comput. Syst.	2009	DBLP DOI BibTeX RDF	Max-leaf, Well-quasiordering, Bandwidth, Kernelization, Parameterized complexity
1	Fedor V. Fomin, Fabrizio Grandoni, Artem V. Pyatkin, Alexey A. Stepanov	Combinatorial bounds via measure and conquer: Bounding minimal dominating sets and applications.	ACM Transactions on Algorithms	2008	DBLP DOI BibTeX RDF	Exact exponential algorithms, domatic number, listing algorithms, measure and conquer, minimum dominating set, minimum set cover
1	Tim Nieberg, Johann Hurink, Walter Kern	Approximation schemes for wireless networks.	ACM Transactions on Algorithms	2008	DBLP DOI BibTeX RDF	bounded growth, Wireless ad-hoc networks, PTAS, maximum independent set, minimum dominating set
1	Christoph Lenzen, Yvonne Anne Oswald, Roger Wattenhofer	What can be approximated locally?: case study: dominating sets in planar graphs.	SPAA	2008	DBLP DOI BibTeX RDF	distributed algorithms, approximation, planar graphs, local algorithms, dominating sets
1	Huy N. Nguyen, Krzysztof Onak	Constant-Time Approximation Algorithms via Local Improvements.	FOCS	2008	DBLP DOI BibTeX RDF
1	L. He, K. Qiu, Z. Z. Shen	Neighbourhood Broadcasting and Broadcasting on the (n, k)-Star Graph.	ICA3PP	2008	DBLP DOI BibTeX RDF	neighbourhood broadcasting, (n and k)-star, disjoint cycle, broadcasting, dominating set, star
1	Andrzej Czygrinow, Michal Hanckowiak, Wojciech Wawrzyniak	Fast Distributed Approximations in Planar Graphs.	DISC	2008	DBLP DOI BibTeX RDF
1	Christoph Lenzen, Roger Wattenhofer	Leveraging Linial's Locality Limit.	DISC	2008	DBLP DOI BibTeX RDF
1	Ayelet Butman, Danny Hermelin, Moshe Lewenstein, Dror Rawitz	Optimization problems in multiple-interval graphs.	SODA	2007	DBLP DOI BibTeX RDF
1	Fabian Kuhn, Thomas Moscibroda	Distributed approximation of capacitated dominating sets.	SPAA	2007	DBLP DOI BibTeX RDF	distributed approximation, capacities, dominating sets, LP relaxation
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	Michael R. Fellows, Frances A. Rosamond	The Complexity Ecology of Parameters: An Illustration Using Bounded Max Leaf Number.	CiE	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	Alexander Grigoriev, Hans L. Bodlaender	Algorithms for Graphs Embeddable with Few Crossings per Edge.	Algorithmica	2007	DBLP DOI BibTeX RDF
1	Federico Malucelli, Sara Nicoloso	Shiftable intervals.	Annals OR	2007	DBLP DOI BibTeX RDF	Complexity, Optimization problems, Interval graphs
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	Fabrizio Grandoni	A note on the complexity of minimum dominating set.	J. Discrete Algorithms	2006	DBLP DOI BibTeX RDF
1	Anuj Dawar, Martin Grohe, Stephan Kreutzer, Nicole Schweikardt	Approximation Schemes for First-Order Definable Optimisation Problems.	LICS	2006	DBLP DOI BibTeX RDF
1	Andrzej Czygrinow, Michal Hanckowiak, Edyta Szymanska	Distributed Approximation Algorithms for Planar Graphs.	CIAC	2006	DBLP DOI BibTeX RDF
1	Andrzej Czygrinow, Michal Hanckowiak	Distributed Almost Exact Approximations for Minor-Closed Families.	ESA	2006	DBLP DOI BibTeX RDF
1	Sylvain Guillemot	Parameterized Problems on Coincidence Graphs.	ISAAC	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	Bin Fu	Theory and Application of Width Bounded Geometric Separator.	STACS	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	Alexander Grigoriev, Hans L. Bodlaender	Algorithms for Graphs Embeddable with Few Crossings Per Edge.	FCT	2005	DBLP DOI BibTeX RDF
1	Rishi Ranjan, Ashraf Saad	Generic Architecture for Power Aware Routing in Wireless Sensor Networks.	LCN	2004	DBLP DOI BibTeX RDF	Core Based Routing, Sensor Networks, Power Aware Routing, Minimum Dominating Set
1	Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer	What cannot be computed locally!	PODC	2004	DBLP DOI BibTeX RDF	approximation hardness, distributed algorithms, locality, lower bounds, dominating set, vertex cover, maximal independent set, maximal matching
1	Farooq Anjum, Dhanant Subhadrabandhu, Saswati Sarkar, Rahul Shetty	On Optimal Placement of Intrusion Detection Modules in Sensor Networks.	BROADNETS	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	Fedor V. Fomin, Dieter Kratsch, Gerhard J. Woeginger	Exact (Exponential) Algorithms for the Dominating Set Problem.	WG	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	Miranca Fischermann, Dieter Rautenbach, Lutz Volkmann	Maximum graphs with a unique minimum dominating set.	Discrete Mathematics	2003	DBLP DOI BibTeX RDF
1	Lichun Bao, J. J. Garcia-Luna-Aceves	Topology management in ad hoc networks.	MobiHoc	2003	DBLP DOI BibTeX RDF	ad hoc networks, connected dominating set, minimum dominating set
1	Donghoon Kim, Bonam Kim, Min-Te Sun	A Simple Protocol for Dominating Set Construction in Mobile Ad Hoc Networks.	ICPP Workshops	2003	DBLP DOI BibTeX RDF
1	Mounire El Houmaidi, Mostafa A. Bassiouni	k-Weighted Minimum Dominating Sets for Sparse Wavelength Converters Placement under Non-uniform Traffic.	MASCOTS	2003	DBLP DOI BibTeX RDF
1	Martin Grohe	Local Tree-Width, Excluded Minors, and Approximation Algorithms.	Combinatorica	2003	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000): 05C83, 05C85, 68W25
1	Ertem Tuncel, Prashant Koulgi, Shankar L. Regunathan, Kenneth Rose	Zero-Error Source Coding with Maximum Distortion Criterion.	DCC	2002	DBLP DOI BibTeX RDF	Zero-error source coding, maximum distortion, JPEG LS, trees, dominating sets, interval graphs
1	Yosuke Kikuchi, Yukio Shibata	On the Domination Numbers of Generalized de Bruijn Digraphs and Generalized Kautz Digraphs.	COCOON	2001	DBLP DOI BibTeX RDF
1	Mirela Damian-Iordache, Sriram V. Pemmaraju	Constant-Factor Approximation Algorithms for Domination Problems on Circle Graphs.	ISAAC	1999	DBLP DOI BibTeX RDF
1	Mirela Damian-Iordache, Sriram V. Pemmaraju	Hardness of Approximating Independent Domination in Circle Graphs.	ISAAC	1999	DBLP DOI BibTeX RDF
1	Afonso Ferreira, Isabelle Guérin Lassous, K. Marcus, Andrew Rau-Chaplin	Parallel Computation on Interval Graphs Using PC CLusters: Algorithms and Experiments.	Euro-Par	1998	DBLP DOI BibTeX RDF
1	Paola Alimonti, Viggo Kann	Hardness of Approximating Problems on Cubic Graphs.	CIAC	1997	DBLP DOI BibTeX RDF
1	Harry B. Hunt III, Madhav V. Marathe, Venkatesh Radhakrishnan, S. S. Ravi, Daniel J. Rosenkrantz, Richard Edwin Stearns	Approximation Schemes Using L-Reductions.	FSTTCS	1994	DBLP DOI BibTeX RDF
1	Madhav V. Marathe, Venkatesh Radhakrishnan, Harry B. Hunt III, S. S. Ravi	Hierarchical Specified Unit Disk Graphs (Extended Abstract).	WG	1993	DBLP DOI BibTeX RDF
1	Zhugou Mo, Kenneth Williams	Algorithms on Block-Complete Graphs.	Great Lakes Computer Science Conference	1989	DBLP DOI BibTeX RDF
1	Nimrod Megiddo, Uzi Vishkin	On Finding a Minimum Dominating Set in a Tournament.	Theor. Comput. Sci.	1988	DBLP DOI BibTeX RDF
1	Peter J. Slater	R-Domination in Graphs.	J. ACM	1976	DBLP DOI BibTeX RDF