Approximating Fault-Tolerant Domination in General Graphs Klaus-Tycho Foerster∗ Abstract In this paper we study the NP-complete problem of finding small k-dominating sets in general graphs, which allow k − 1 nodes to

First Page		Document Content
Date: 2015-05-18 12:16:23 Graph theory Mathematics Computational complexity theory NP-complete problems Dominating set Independent set Vertex cover Connected dominating set Set cover problem Line graph Metric k-center Domatic number		Approximating Fault-Tolerant Domination in General Graphs Klaus-Tycho Foerster∗ Abstract In this paper we study the NP-complete problem of finding small k-dominating sets in general graphs, which allow k − 1 nodes to Add to Reading List Source URL: www.tik.ee.ethz.ch Download Document from Source Website File Size: 385,33 KB Share Document on Facebook

	Connected Dominating Set in Graphs Without Long Paths And Cycles Eglantine Camby1 and Oliver Schaudt2 1 D´epartement de Math´ematique, Universit´e Libre de Bruxelles, Boulevard du Triomphe, 1050 DocID: 1ojNc - View Document
	Approximating Fault-Tolerant Domination in General Graphs Klaus-Tycho Förster ETH Zurich – Distributed Computing – www.disco.ethz.ch DocID: 1lNO5 - View Document
	Approximating Fault-Tolerant Domination in General Graphs Klaus-Tycho Foerster∗ Abstract In this paper we study the NP-complete problem of finding small k-dominating sets in general graphs, which allow k − 1 nodes to DocID: 1lFOT - View Document
	Correlation Clustering and Two-edge-connected Augmentation for Planar Graphs Philip N. Klein1 , Claire Mathieu2,3 , and Hang Zhou3 1 Brown University, United States DocID: 1a69s - View Document
	CCCG 2010, Winnipeg MB, August 9–11, 2010 3D Local Algorithm for Dominating Sets of Unit Disk Graphs A.E. Abdallah and T. Fevens and J. Opatrny∗ Abstract DocID: 18WIc - View Document