In this paper, we consider the question of computing sparse subgraphs for any input directed graph \(G=(V,E)\) on \(n\) vertices and \(m\) edges, that preserves reachability and/or strong connectivity structures. We show \(O(n+\min\{|{\mathcal{P}}|\sqrt{n},n\sqrt{|{\mathcal{P} }|}\})\) bound a subgraph is an \(1\) -fault-tolerant preserver given vertex-pair set \({\mathcal{P}}\subseteq V\times V\) , i.e., it between pair in \({\mathcal{P}}\) under single edge (or vertex) failure. Our result...

Let G=(V,E) be an n-vertices m-edges directed graph. s∈ V any designated source vertex. We address the problem of single reachability (SSR) from s in presence failures vertices/edges. show that for every k≥ 1, there is a subgraph H G with at most 2k n edges preserves even after failure k edges. Formally, given set F edges, vertex u∈ reachable G∖ if and only u H∖ F. call k-Fault Tolerant Reachability Subgraph (k-FTRS). prove also matching lower bound Ω(2kn) such subgraphs. Our results extend...

Summary The present study pertains to the development of a foundation model for predicting behavior geosynthetic reinforcement railway track system rested on soft clay subgrade. ballast and sub‐ballast layers have been idealized by Pasternak shear layer. layer is represented stretched rough elastic membrane. Burger has used characterize Numerical solutions obtained adopting finite difference scheme combined with non‐dimensioning governing equations proposed model. results confirm that quite...

Let G=(V,E) be an n-vertices m-edges directed graph. s inV any designated source vertex. We address the problem of reporting reachability information from under two vertex failures. show that it is possible to compute in polynomial time O(n) size data structure for query v, and pair failed vertices f_1, f_2, answers O(1) whether or not there exists a path v G\{f_1,f_2}. For simpler case single failure such can obtained using dominator-tree celebrated work Lengauer Tarjan [TOPLAS 1979,...

Depth first search (DFS) tree is a fundamental data structure for solving various problems in graphs. It well known that it takes $O(m+n)$ time to build DFS given undirected graph $G=(V,E)$ on $n$ vertices and $m$ edges. We address the problem of maintaining when undergoing updates (insertion deletion or edges). present following results this problem: (1) Fault tolerant tree: There exists size $\tilde{O}(m)$ (where $\tilde{O}$ hides polylogarithmic factors) which can be preprocessed such any...

Given an undirected graph G = (V, E) on n vertices and m edges, we address the problem of maintaining a DFS tree when is undergoing updates (insertion deletion or edges). We present following results for this problem.1. Fault tolerant tree:There exists data structure size O(m) 1 such that given any set F failed G\F can be reported in O(n|F|) time.2. Fully dynamic fully algorithm takes worst case O([EQUATION]) time per update arbitrary online sequence updates.3. Incremental tree:Given edge...

Depth first search (DFS) tree is a fundamental data structure for solving various problems in graphs. It well known that it takes $O(m+n)$ time to build DFS given undirected graph $G=(V,E)$ on $n$ vertices and $m$ edges. We address the problem of maintaining when undergoing {\em updates} (insertion deletion or edges). present following results this problem. (a) Fault tolerant tree: There exists size ${O}(m ~polylog~ n)$ such any set ${\cal F}$ failed edges, $G\setminus {\cal can be reported...

An f-edge fault-tolerant distance sensitive oracle (f-DSO) with stretch σ ≥ 1 is a data structure that preprocesses given undirected, unweighted graph G n vertices and m edges, positive integer f. When queried pair of s, t set F at most f it returns σ-approximation the s-t-distance in G−F.

A dominating set $D$ for a graph $G$ is subset of $V(G)$ such that any vertex not in has at least one neighbor $D$. The domination number $\gamma(G)$ the size minimum G. Vizing's conjecture from 1968 states Cartesian product graphs and $H$, $\gamma(G)\gamma(H) \leq \gamma(G \Box H)$, Clark Suen (2000) proved 2 H)$. In this paper, we modify approach to prove variety similar bounds related total paired domination, also extend these $n$-Cartesian $A^1$ through $A^n$.

Let $G$ be a directed graph with $n$ vertices, $m$ edges, and designated source vertex $s$. We address the problem of single-source reachability (SSR) from $s$ in presence failures vertices/edges. show that for every $k\geq1$, there is subgraph $H$ at most $2^kn$ edges preserves even after failure any $k$ edges. Formally, given set $F$ $v\in V(G)$ reachable $G\setminus F$ if only $v$ $H\setminus F$. call $k$-fault tolerant ($\textsc{$k$-FTRS}$). also prove matching lower bound $\Omega(2^kn)$...

Real life graphs and networks are prone to failure of nodes (vertices) links (edges). In particular, for a pair s t failing edge e in an n-vertex unweighted graph G=(V(G),E(G)), the replacement path pi_{G-e}(s,t) is shortest s-t that avoids e. this paper we present several efficient constructions that, every (s,t) \in S x T, where S, T \subseteq V(G), E(G), maintain collection all pi_{G-e}(s,t), either implicitly (i.e., through compact data structures a.k.a. distance sensitivity oracles...

We study graph realization problems from a distributed perspective. The problem is naturally applicable to the construction of overlay networks that must satisfy certain degree or connectivity properties, and we it in node capacitated clique (NCC) model computing, recently introduced for representing peer-to-peer networks.We focus on two central variants, degree-sequence minimum threshold-connectivity realization. In sequence problem, each v associated with d(v), resulting realizable if...

We consider the problem of realizable interval-sequences. An interval sequence comprises n integer intervals [a_i,b_i] such that 0 <= a_i b_i n-1, and is said to be graphic/realizable if there exists a graph with degree sequence, say, D=(d_1,...,d_n) satisfying condition d_i b_i, for each i in [1,n]. There characterisation (also implying an O(n) verifying algorithm) known realizability interval-sequences, which generalization Erdos-Gallai graphic sequences. However, given any...

We study graph realization problems from a distributed perspective.The problem is naturally applicable to the construction of overlay networks that must satisfy certain degree or connectivity properties, and we it in node capacitated clique (NCC) model computing, recently introduced for representing peer-to-peer networks.We focus on two central variants, degree-sequence minimum threshold-connectivity realization.In sequence problem, each v associated with d(v), resulting realizable if...