We give a (1+ϵ)-approximate distance oracle with O(1) query time for an undirected planar graph G with n vertices and non-negative edge lengths. For ϵ>0 and any two vertices u and v in G, our oracle ...gives a distance d˜(u,v) with stretch (1+ϵ) in O(1) time. The oracle has size O(nlogn((logn)/ϵ+f(ϵ))) and pre-processing time O(nlogn((log3n)/ϵ2+f(ϵ))), where f(ϵ)=2O(1/ϵ). This is the first (1+ϵ)-approximate distance oracle with O(1) query time independent of ϵ and the size and pre-processing time nearly linear in n, and improves the query time O(1/ϵ) of previous (1+ϵ)-approximate distance oracle with size nearly linear in n.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
Water utilities face a challenge in maintaining a good quality of service under a wide range of operational management and failure conditions. Tools for assessing the resilience of water distribution ...networks are therefore essential for both operational and maintenance optimization. In this paper, a novel graph-theoretic approach for the assessment of resilience for large scale water distribution networks is presented. This is of great importance for the management of large scale water distribution systems, most models containing up to hundreds of thousands of pipes and nodes. The proposed framework is mainly based on quantifying the redundancy and capacity of all possible routes from demand nodes to their supply sources. This approach works well with large network sizes since it does not rely on precise hydraulic simulations, which require complex calibration processes and computation, while remaining meaningful from a physical and a topological point of view. The proposal is also tailored for the analysis of sectorised networks through a novel multiscale method for analysing connectivity, which is successfully tested in operational utility network models made of more than 100,000 nodes and 110,000 pipes.
Full text
Available for:
CEKLJ, EMUNI, FIS, FZAB, GEOZS, GIS, IJS, IMTLJ, KILJ, KISLJ, MFDPS, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, SBMB, SBNM, UKNU, UL, UM, UPUK, VKSCE, ZAGLJ
Riordan graphs I: Structural properties Cheon, Gi-Sang; Jung, Ji-Hwan; Kitaev, Sergey ...
Linear algebra and its applications,
10/2019, Volume:
579
Journal Article
Peer reviewed
Open access
In this paper, we use the theory of Riordan matrices to introduce the notion of a Riordan graph. The Riordan graphs are a far-reaching generalization of the well known and well studied Pascal graphs ...and Toeplitz graphs, and also some other families of graphs. The Riordan graphs are proved to have a number of interesting (fractal) properties, which can be useful in creating computer networks with certain desirable features, or in obtaining useful information when designing algorithms to compute values of graph invariants. The main focus in this paper is the study of structural properties of families of Riordan graphs obtained from infinite Riordan graphs, which includes a fundamental decomposition theorem and certain conditions on Riordan graphs to have an Eulerian trail/cycle or a Hamiltonian cycle. We will study spectral properties of the Riordan graphs in a follow up paper.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
Let Kv be the complete graph of order v. A (K2,K1,3)-URD(v;r,s) is a decomposition of Kv into a set of subgraphs which can be partitioned into r parallel classes containing only copies of K2 and s ...parallel classes containing only copies of K1,3, such that every point of Kv appears exactly once in some subgraphs of each parallel class. S. Küçükçifçi et al. have completely solved the existence of a (K2,K1,3)-URD(v;r,s) with minimum number of 1-factors and with 14 possible exceptions. In this paper, we shall give some new constructions for (K2,K1,3)-URDs, and completely solve the existence of a (K2,K1,3)-URD(v;r,s)for any admissible parameters v,r and s.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
Let
=
) be a rectangular solid grid graph and 𝒜(
) be a minimum length Eulerian augmentation of
. Let
, . . .,
∈ ℕ such that ∑
=
(𝒜(
where 2(
+
)
= 2
. In this paper, we exhibit a constructive ...procedure providing an edge-disjoint decomposition of 𝒜 (
) into closed trails
, . . .,
such that
=
Subexponential time approximation algorithms are presented for the U
nique
G
ames
and S
mall
-S
et
E
xpansion
problems. Specifically, for some absolute constant
c
, the following two algorithms are ...presented.
(1) An exp(
kn
ϵ
)-time algorithm that, given as input a
k
-alphabet unique game on
n
variables that has an assignment satisfying 1-ϵ
c
fraction of its constraints, outputs an assignment satisfying 1-ϵ fraction of the constraints.
(2) An exp(
n
ϵ
/δ)-time algorithm that, given as input an
n
-vertex regular graph that has a set
S
of δ
n
vertices with edge expansion at most
ϵ
c
, outputs a set
S'
of at most δ
n
vertices with edge expansion at most ϵ.
subexponential algorithm is also presented with improved approximation to M
ax
C
ut
, S
parsest
C
ut
, and V
ertex
C
over
on some interesting subclasses of instances. These instances are graphs with low
threshold rank
, an interesting new graph parameter highlighted by this work.
Khot's Unique Games Conjecture (UGC) states that it is
NP
-hard to achieve approximation guarantees such as ours for U
nique
G
ames
. While the results here stop short of refuting the UGC, they do suggest that U
nique
G
ames
are significantly easier than
NP
-hard problems such as M
ax
3-S
at
, M
ax
3-
Lin
, L
abel
C
over
, and more, which are believed not to have a subexponential algorithm achieving a nontrivial approximation ratio.
Of special interest in these algorithms is a new notion of graph decomposition that may have other applications. Namely, it is shown for every ϵ >0 and every regular
n
-vertex graph
G
, by changing at most δ fraction of
G
's edges, one can break
G
into disjoint parts so that the stochastic adjacency matrix of the induced graph on each part has at most
n
ϵ
eigenvalues larger than 1-η, where η depends polynomially on ϵ. The subexponential algorithm combines this decomposition with previous algorithms for U
nique
G
ames
on graphs with few large eigenvalues Kolla and Tulsiani 2007; Kolla 2010.
Full text
Available for:
IZUM, KILJ, NUK, PILJ, SAZU, UL, UM, UPUK
A Gallai coloring of a complete graph Kn is an edge coloring without triangles colored with three different colors. A sequence e1≥⋯≥ek of positive integers is an (n,k)-sequence if ∑i=1kei=n2. An ...(n,k)-sequence is a G-sequence if there is a Gallai coloring of Kn with k colors such that there are ei edges of color i for all i,1≤i≤k. Gyárfás, Pálvölgyi, Patkós and Wales proved that for any integer k≥3 there exists an integer g(k) such that every (n,k)-sequence is a G-sequence if and only if n≥g(k). They showed that g(3)=5,g(4)=8 and 2k−2≤g(k)≤8k2+1.
We show that g(5)=10 and give almost matching lower and upper bounds for g(k) by showing that with suitable constants α,β>0, αk1.5lnk≤g(k)≤βk1.5 for all sufficiently large k.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
Recently, we have introduced two graph-decomposition theorems based on a new graph product, motivated by applications in the context of synchronising periodic real-time processes. This ...vertex-removing synchronised product (VRSP) is based on modifications of the well-known Cartesian product and is closely related to the synchronised product due to Wöhrle and Thomas.
Here, we show how we can relax the requirements of these two graph-decomposition theorems.
A double-star Sq1,q2 is the graph consisting of the union of two stars, K1,q1 and K1,q2, together with an edge joining their centers. The spectrum for Sq1,q2-designs, i.e., the set of all the n∈N ...such that an Sq1,q2-design of the order n exists, is well-known when q1=q2=2. In this article, S2,2-designs satisfying additional properties are investigated. We determine the spectrum for S2,2-designs that can be transformed into (K4−e)-designs by a double squash (bi-squash) passing through middle designs whose blocks are copies of a bull (the graph consisting of a triangle and two pendant edges). Here, the use of the difference method enables obtaining cyclic decompositions and determining the spectrum for cyclic S2,2-designs that can be purely bi-squashed into cyclic (K4−e)-designs (the middle bull designs are also cyclic).
Let Γ(Zn ) be the zero-divisor graph whose vertices are the nonzero zero divisors of Zn , and such that two vertices u,υ are adjacent if n divides uυ. Let \({K}_{p-1}^{f}\) denotes the fuzzy complete ...graph on p − 1 vertices and let \({K}_{p-1}^{f}\) denote a fuzzy star with p − 1 edges. In this paper, we have analyzed the fuzzy zero divisor graph of Γf (Zp 3) is decomposition into 1-complete \({K}_{p-1}^{f}\) and p(p − 1) copies of star graph \({K}_{p-1}^{f}\) where p is prime number and p > 2.
PDF
