NDLI: On connected domination in unit ball graphs

Content Provider	Springer Nature Link
Author	Butenko, Sergiy Kahruman Anderoglu, Sera Ursulenko, Oleksii
Copyright Year	2010
Abstract	Given a simple undirected graph, the minimum connected dominating set problem is to find a minimum cardinality subset of vertices D inducing a connected subgraph such that each vertex outside D has at least one neighbor in D. Approximations of minimum connected dominating sets are often used to represent a virtual routing backbone in wireless networks. This paper first proposes a constant-ratio approximation algorithm for the minimum connected dominating set problem in unit ball graphs and then introduces and studies the edge-weighted bottleneck connected dominating set problem, which seeks a minimum edge weight in the graph such that the corresponding bottleneck subgraph has a connected dominating set of size k. In wireless network applications this problem can be used to determine an optimal transmission range for a network with a predefined size of the virtual backbone. We show that the problem is hard to approximate within a factor better than 2 in graphs whose edge weights satisfy the triangle inequality and provide a 3-approximation algorithm for such graphs. We also show that for fixed k the problem is polynomially solvable in unit disk and unit ball graphs.
Starting Page	195
Ending Page	205
Page Count	11
File Format	PDF
ISSN	18624472
Journal	Optimization Letters
Volume Number	5
Issue Number	2
e-ISSN	18624480
Language	English
Publisher	Springer-Verlag
Publisher Date	2010-06-24
Publisher Place	Berlin, Heidelberg
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Connected dominating set Unit ball graph Wireless networks Numerical and Computational Physics Operations Research/Decision Theory Computational Intelligence Optimization
Content Type	Text
Resource Type	Article
Subject	Control and Optimization Business, Management and Accounting

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

A PTAS for minimum d-hop connected dominating set in growth-bounded graphs

A distributed approximation algorithm for the bottleneck connected dominating set problem

A PTAS for minimum connected dominating set in 3-dimensional Wireless sensor networks

Wireless networking, dominating and packing

Adaptive energy efficient sensor scheduling for wireless sensor networks

On approximation of dominating tree in wireless sensor networks

A framework of distributed indexing and data dissemination in large scale wireless sensor networks

The connected p-median problem on block graphs

On positive-influence target-domination

On connected domination in unit ball graphs

Similar Documents

A PTAS for minimum d-hop connected dominating set in growth-bounded graphs

A distributed approximation algorithm for the bottleneck connected dominating set problem

A PTAS for minimum connected dominating set in 3-dimensional Wireless sensor networks

Wireless networking, dominating and packing

Adaptive energy efficient sensor scheduling for wireless sensor networks

On approximation of dominating tree in wireless sensor networks

A framework of distributed indexing and data dissemination in large scale wireless sensor networks

The connected p-median problem on block graphs

On positive-influence target-domination

On connected domination in unit ball graphs