The Wireless Mesh Network (WMN) has already been recognized as a promising broadband access network technology from both academic and commercial perspective. In order to improve the performance of ...WMNs, extensive research efforts have been dedicated towards finding means to increase the number of simultaneous transmissions in the network while avoiding signal interference among radios. In case of WMNs based on IEEE 802.11 b/g standards, most recent research works have relied upon the usage of orthogonal channels for solving the Channel Assignment (CA) problem. In this paper, we explore the possibility of exploiting Partially Overlapped Channels (POCs) by introducing a novel game theoretic distributed CA algorithm. Our proposed algorithm outperforms both the conventional orthogonal channel approach and the recent heuristic CA algorithms using POC. The proposed algorithm is shown to achieve near-optimal performance in the average case. In addition, the upper bound Price of Anarchy for Multi-Radio Multi-Channel (MRMC) networks is derived to evaluate the effectiveness of the proposed approach.
Anti-k-labeling of graphs Guan, Xiaxia; Zhang, Shurong; Li, Rong-hua ...
Applied mathematics and computation,
12/2019, Volume:
363
Journal Article
Peer reviewed
It is well known that the labeling problems of graphs arise in many (but not limited to) networking and telecommunication contexts. In this paper we introduce the anti-k-labeling problem of graphs ...which we seek to minimize the similarity (or distance) of neighboring nodes. For example, in the fundamental frequency assignment problem in wireless networks where each node is assigned a frequency, it is usually desirable to limit or minimize the frequency gap between neighboring nodes so as to limit interference.
Let k ≥ 1 be an integer and ψ is a labeling function (anti-k-labeling) from V(G) to {1,2,…,k} for a graph G. A no-hole anti-k-labeling is an anti-k-labeling using all labels between 1 and k. We define wψ(e)=|ψ(u)−ψ(v)| for an edge e=uv and wψ(G)=min{wψ(e):e∈E(G)} for an anti-k-labeling ψ of the graph G. The anti-k-labeling number of a graph G, λk(G), is max {wψ(G): ψ}. In this paper, we first show that λk(G)=⌊k−1χ−1⌋, and the problem that determines the anti-k-labeling number of graphs is NP-hard. We mainly obtain the lower bounds on no-hole anti-n-labeling number for trees, grids and n-cubes.
Let G be a simple graph. Suppose f is a mapping from V(G) to nonnegative integers. If, for any two adjacent vertices u and v of G, |f(u)−f(v)|≥2, then f is called a 2-distant coloring of G. In this ...paper, we introduce a relaxation of 2-distant coloring of a graph. Let t be a nonnegative integer. Suppose f is a mapping from V(G) to nonnegative integers. If adjacent vertices receive different integers and for each vertex u of G, the number of neighbors v of u with |f(v)−f(u)|=1 is at most t, then f is called a t-relaxed 2-distant coloring of G. If t=0 then f is just a 2-distant coloring of G. The span of f, denote by sp(f), is the difference between the maximum and minimum integers used by f. The minimum span of a t-relaxed 2-distant coloring of G, is called t-relaxed 2-distant coloring span of G, denoted by sp2t(G). Suppose G is a graph. Let γ:V(G)→Z+ be a function defined on V(G). A γ-relaxed 2-distant coloring of G with span k is a mapping f from V(G) to {0,1,…,k} such that f(u)≠f(v) for any two adjacent vertices u and v and each vertex u of G has at most γ(u) neighbors v with |f(v)−f(u)|=1.
In this paper, we prove that, for any two positive integers t and k with k≥2, deciding if sp2t(G)≤k for a graph G is NP-complete, except the case when t=1 and k=2 which is polynomial-time solvable. Let t be any nonnegative integer. It is easy to see that sp2t(G)≤6 for any planar graph G and sp2t(G)≤4 for any outerplanar graph G. We prove that, for any two positive integers t and k with k∈{2,3,4,5}, deciding if sp2t(G)≤k for a planar graph G is NP-complete, except the case when t=1 and k=2 which is polynomial-time solvable. We present examples to illustrate that there is no constant integer t such that every planar graph has a t-relaxed 2-distant coloring of span 5 and there is no constant integer t such that every outerplanar graph has a t-relaxed 2-distant coloring of span 3. We introduce pseudo ear decomposition and simple pseudo ear decomposition of a graph and show that a graph is outerplanar if and only if it admits a simple pseudo ear decomposition. Using this result, we show that each outerplanar graph has a γ-relaxed 2-distant coloring with span 3, where γ(v)=⌈d(v)2⌉ for each vertex v of G and the function γ is sharp in some sense, and that every triangle-free outerplanar graph has a 1-relaxed 2-distant coloring with span 3.
For a simple connected graph
G
= (
V
(
G
),
E
(
G
)) and a positive integer
k
, a radio
k
-labelling of
G
is a mapping
f
:
V
(
G
)
→
{
0
,
1
,
2
,
…
}
such that
|
f
(
u
)
−
f
(
v
)
|
≥
k
+
1
−
d
(
u
...,
v
)
for each pair of distinct vertices
u
and
v
of
G
, where
d
(
u
,
v
) is the distance between
u
and
v
in
G
. The
radio k-chromatic number
is the minimum span of a radio
k
-labeling of
G
. In this article, we study the radio
k
-labelling problem for complete
m
-ary trees
T
m
,
h
and determine the exact value of radio
k
-chromatic number for these trees when
k
≥ 2
h
− 1.
Radio Graceful Labelling of Graphs Saha, Laxman
Theory and applications of graphs (Statesboro, Ga.),
05/2020, Volume:
7, Issue:
1
Journal Article
Peer reviewed
Open access
Radio labelling problem of graphs have their roots in communication problem known as \emph{Channel Assignment Problem}. For a simple connected graph $G=(V(G), E(G))$, a radio labeling is a mapping $f ...\colon V(G)\rightarrow \{0,1,2,\ldots\}$ such that $|f(u)-f(v)|\geq {\rm diam}(G)+1-d(u,v)$ for each pair of distinct vertices $u,v\in V(G)$, where $\rm{diam}(G)$ is the diameter of $G$ and $d(u,v)$ is the distance between $u$ and $v$. A radio labeling $f$ of a graph $G$ is a \emph{radio graceful labeling} of $G$ if $f(V(G)) = \{0,1,\ldots, |V(G)|-1\}$. A graph for which a radio graceful labeling exists is called \emph{radio graceful}. In this article, we study radio graceful labeling for general graphs in terms of some new parameters.
For a simple connected graph
and a positive integer
with
, a radio
-coloring of
is a mapping
such that
holds for each pair of distinct vertices
and
of
, where
is the diameter of
and
is the distance ...between
and
in
. The span of a radio
-coloring
is the number
. The main aim of the radio
-coloring problem is to determine the minimum span of a radio
-coloring of
, denoted by
. Due to NP-hardness of this problem, people are finding lower bounds for
for particular families of graphs or general graphs
. In this article, we concentrate on finding upper bounds of radio
-chromatic number for general graphs and in consequence a coloring scheme depending on a partition of the vertex set
. We apply these bounds to cycle graph
and hypercube
and show that it is sharp when
is close to the diameter of these graphs.
For a positive integer k with 1⩽k⩽q, a radio k-coloring of a simple connected graph G=(V(G),E(G)) is a mapping f:V(G)→{0,1,2,…} such that |f(u)−f(v)|⩾k+1−d(u,v) for each pair of distinct vertices ...u,v∈V(G), where q is the diameter of G and d(u,v) is the distance between u and v. The span rck(f) of f is defined as maxu∈V(G)f(u). The radio k-chromatic number rck(G) of G is min{rck(f)} over all radio k-colorings f of G. In this paper, we give a lower bound of rck(G) for general graph G and discuss the sharpness in the particular case when k=q,q−1. In some cases we give the necessary and sufficient conditions for equality of this bound. As an application we obtain lower bounds of the radio k-chromatic number for the graphs Cn,Pm□Pn,Km□Cn,Pm□Cn and Qn. Moreover, we show that the lower bound of rck(Qn) is an improvement of the existing one.
In this article, we propose a novel method of formulating an NP-hard wireless channel assignment problem as a higher-order unconstrained binary optimization (HUBO), where the Grover adaptive search ...(GAS) is used to provide a quadratic speedup for solving the problem. The conventional method relies on a one-hot encoding of the channel indices, resulting in a quadratic formulation. By contrast, we conceive ascending and descending binary encodings of the channel indices, construct a specific quantum circuit, and derive the exact numbers of qubits and gates required by GAS. Our analysis clarifies that the proposed HUBO formulation significantly reduces the number of qubits and the query complexity compared with the conventional quadratic formulation. This advantage is achieved at the cost of an increased number of quantum gates, which we demonstrate can be reduced by our proposed descending binary encoding.
A Radio mean labeling of a connected graph <inline-formula> <tex-math notation="LaTeX">G </tex-math></inline-formula> is an injective function <inline-formula> <tex-math notation="LaTeX">h ...</tex-math></inline-formula> from the vertex set, <inline-formula> <tex-math notation="LaTeX">V(G) </tex-math></inline-formula>, to the set of natural numbers <inline-formula> <tex-math notation="LaTeX">N </tex-math></inline-formula> such that for any two distinct vertices <inline-formula> <tex-math notation="LaTeX">x </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">y </tex-math></inline-formula> of <inline-formula> <tex-math notation="LaTeX">G </tex-math></inline-formula>, <inline-formula> <tex-math notation="LaTeX">\left \lceil{ \frac {h\left ({x }\right)+h(y)}{2} }\right \rceil \mathrm {\ge }diam\mathrm {+1-}d(x,y) </tex-math></inline-formula>. The radio mean number of <inline-formula> <tex-math notation="LaTeX">h </tex-math></inline-formula>, <inline-formula> <tex-math notation="LaTeX">rmn(h) </tex-math></inline-formula>, is the maximum number assigned to any vertex of <inline-formula> <tex-math notation="LaTeX">G </tex-math></inline-formula>. The radio mean number of <inline-formula> <tex-math notation="LaTeX">G </tex-math></inline-formula>, <inline-formula> <tex-math notation="LaTeX">rmn(G) </tex-math></inline-formula>, is the minimum value of <inline-formula> <tex-math notation="LaTeX">rmn(h) </tex-math></inline-formula>, taken over all radio mean labeling <inline-formula> <tex-math notation="LaTeX">h </tex-math></inline-formula> of <inline-formula> <tex-math notation="LaTeX">G </tex-math></inline-formula>. This work has three contributions. The first one is proving two theorems which find the radio mean number for cycles and paths. The second contribution is proposing an approximate algorithm which finds an upper bound for radio mean number of a given graph. The third contribution is that we introduce a novel integer linear programing formulation for the radio mean problem. Finally, the experimental results analysis and statistical test proved that the Integer Linear Programming Model overcame the proposed approximate algorithm according to CPU time only. On the other hand, both the Integer Linear Programming Model and the proposed approximate algorithm had the same upper bound of the radio mean number of <inline-formula> <tex-math notation="LaTeX">G </tex-math></inline-formula>.
PDF
