A new bound on maximum independent set and minimum connected dominating set in unit disk graphs

Yingfan L. Du; Hongmin W. Du

doi:10.1007/s10878-013-9690-0

A new bound on maximum independent set and minimum connected dominating set in unit disk graphs

Yingfan L. Du
, Hongmin W. Du

Highland Park High School

Research output: Contribution to journal › Article › peer-review

Abstract

It is a conjecture that in any unit disk graph G, α(G)≤3·_γc(G)+3 where α(G) is the size of the maximum independent set in G and γc(G) is the size of minimum connected dominating set in G. In this paper, we show that in any unit disk graph G, α(G)≤3.399·γc(G)+4.874. Currently, this is the best-known bound.

Original language	English
Pages (from-to)	1173-1179
Number of pages	7
Journal	Journal of Combinatorial Optimization
Volume	30
Issue number	4
DOIs	https://doi.org/10.1007/s10878-013-9690-0
State	Published - Nov 1 2015
Externally published	Yes

ASJC Scopus Subject Areas

Computer Science Applications
Discrete Mathematics and Combinatorics
Control and Optimization
Computational Theory and Mathematics
Applied Mathematics

Keywords

Maximum independent set
Minimum connected dominating set
Unit disk graphs

Access to Document

10.1007/s10878-013-9690-0

Cite this

@article{e236b93daf444792bd48deda68be220a,

title = "A new bound on maximum independent set and minimum connected dominating set in unit disk graphs",

abstract = "It is a conjecture that in any unit disk graph G, α(G)≤3·γc(G)+3 where α(G) is the size of the maximum independent set in G and γc(G) is the size of minimum connected dominating set in G. In this paper, we show that in any unit disk graph G, α(G)≤3.399·γc(G)+4.874. Currently, this is the best-known bound.",

keywords = "Maximum independent set, Minimum connected dominating set, Unit disk graphs",

author = "Du, \{Yingfan L.\} and Du, \{Hongmin W.\}",

note = "Publisher Copyright: {\textcopyright} 2013, Springer Science+Business Media New York.",

year = "2015",

month = nov,

day = "1",

doi = "10.1007/s10878-013-9690-0",

language = "English",

volume = "30",

pages = "1173--1179",

journal = "Journal of Combinatorial Optimization",

issn = "1382-6905",

publisher = "Springer Netherlands",

number = "4",

}

TY - JOUR

T1 - A new bound on maximum independent set and minimum connected dominating set in unit disk graphs

AU - Du, Yingfan L.

AU - Du, Hongmin W.

PY - 2015/11/1

Y1 - 2015/11/1

N2 - It is a conjecture that in any unit disk graph G, α(G)≤3·γc(G)+3 where α(G) is the size of the maximum independent set in G and γc(G) is the size of minimum connected dominating set in G. In this paper, we show that in any unit disk graph G, α(G)≤3.399·γc(G)+4.874. Currently, this is the best-known bound.

AB - It is a conjecture that in any unit disk graph G, α(G)≤3·γc(G)+3 where α(G) is the size of the maximum independent set in G and γc(G) is the size of minimum connected dominating set in G. In this paper, we show that in any unit disk graph G, α(G)≤3.399·γc(G)+4.874. Currently, this is the best-known bound.

KW - Maximum independent set

KW - Minimum connected dominating set

KW - Unit disk graphs

UR - https://www.scopus.com/pages/publications/84944197205

UR - https://www.scopus.com/pages/publications/84944197205#tab=citedBy

U2 - 10.1007/s10878-013-9690-0

DO - 10.1007/s10878-013-9690-0

M3 - Article

AN - SCOPUS:84944197205

SN - 1382-6905

VL - 30

SP - 1173

EP - 1179

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

IS - 4

ER -

A new bound on maximum independent set and minimum connected dominating set in unit disk graphs

Abstract

ASJC Scopus Subject Areas

Keywords

Access to Document

Other files and links

Fingerprint

Cite this