Compact Routing

Efficient parallel algorithms are presented, on the CREW PRAM model, for generating a succinct encoding of all pairs shortest path information in a directed planar graph G with real-valued edge costs but no negative cycles. We assume that a planar embedding of G is given, togetber with a set of q faces that cover all the vertices. Then our algorithm runs in O(log 2 n) time and employs O{nq + M(q)) processors (where M(t) is the number of processors required to multiply two t x t matrices in O(log t) time). Let us note here that whenever q < n then our processor bound is better than the best previous one (M(n)). O(log 2 n) time, n-processor algorithms are presented for various subproblems, including that of generating all pairs shortest path information in a directed outerplanar graph. Our work is based on the fundamental hammock-decomposition technique ofG. Frederickson. We achieve this decomposition in O(log n log* n) parallel time by using O(n) processors. The hammock-decomposition seems to be a fundamental operation that may help in improving efficiency of many parallel (and sequential) graph algorithms.

Interval Routing is a routing method that was proposed in order to reduce the size of the routing tables by using intervals and was extensively studied and implemented. Some variants of the original method were also deÿned and studied. The question of characterizing networks which support optimal (i.e., shortest path) Interval Routing has been thoroughly investigated for each of the variants and under di erent models, with only partial answers, both positive and negative, given so far. In this paper, we study the characterization problem under the most basic model (the one unit cost), and with the most restrictive memory requirements (one interval per edge). We prove that this problem is NP-hard (even for the restricted class of graphs of diameter at most 3). Our result holds for all variants of Interval Routing. It signiÿcantly extends some related NP-hardness result, and implies that, unless P = NP, partial characterization results of some classes of networks which support shortest path Interval Routing, cannot be pushed further to lead to e cient characterizations for these classes.

Interval routing scheme (k-IRS) is a compact routing scheme on general networks. It has been studied extensively and recently been implemented on the latest generation INMOS Transputer Router chip. In this paper we introduce an extension of the Interval Routing Scheme k-IRS to the multidimensional case (k,d)-MIRS, where k is the number of intervals and d is the number of dimensions. Whereas k-IRS only represents compactly a single shortest path between any two nodes, with this new extension we are able to represent all shortest paths compactly. This is useful for fault-tolerance and traffic distribution in a network. We study efficient representations of all shortest paths between any pair of nodes for general network topologies, for product graphs and for specific interconnection networks such as rings, grids, tori, hypercubes and chordal rings. For these interconnection networks we show that for about the same space complexity as k-IRS we can represent all shortest paths in (k,d)-MIRS (as compared to only a single shortest path in k-IRS). Moreover, trade-offs are derived between the dimension d and the number of intervals k in multidimensional interval routing schemes on hypercubes, grids and tori,

* Copyright 2007, Uzi Vishkin. These class notes reflect the theorertical part in the Parallel Algorithms course at UMD. The parallel programming part and its computer architecture context within the PRAM-On-Chip Explicit Multi-Threading (XMT) platform is provided through the XMT home page www.umiacs.umd.edu/users/vishkin/XMT and the class home page. Comments are welcome: please write to me using my last name at umd.edu

In this paper we propose compact routing schemes having space and time complexities comparable to a 2-Interval Routing Scheme for the class of networks decomposable as Layered Cross Product (LCP) of rooted trees. As a consequence, we are able to design a 2-IntervM Routing Scheme for butterflies, meshes of trees and fat trees using a fast local routing algorithm. Finally, we show that a compact routing scheme for networks which are LCP of general graphs cannot be found by any only using shortest paths information on the factors.

Dedicated to Paul Erd} os on the occasion of his 80th birthday Paul Erd} os has conjectured that Menger's theorem extends to in nite graphs in the following way: whenever A; B are two sets of vertices in an in nite graph, there exist a set of disjoint A{B paths and an A{B separator in this graph so that the separator consists of a choice of precisely one vertex from each of the paths. We prove this conjecture for graphs that contain a set of disjoint paths to B from all but countably many vertices of A. In particular, the conjecture is true when A is countable.

A graph is an X-graph of Y-graphs (or two-level clustered graph) if its vertices can be partitioned into subsets (called clusters) such that each cluster induces a graph belonging to the given class Y and the graph of the clusters belongs to another given class X. Two-level clustered graphs are a useful and interesting concept in graph drawing. We consider the complexity of recognizing two-level clustered graphs. We prove that, for a given integer k ¿ 2, it is NP-complete to decide whether or not a graph is a path of length k − 1 of paths (cycles). This solves a problem posed by Schreiber, Skodinis and Brandenburg. Similar reductions show that it is NP-complete to decide whether or not a graph is a k-star/k-clique of paths (cycles). In contrast, we show that k-graphs of path (cycles) can be recognized in polynomial time when the inputs are restricted to graphs of bounded treewidth.

Let G be a class of graphs. A graph G has G-width k if there are k independent sets N 1 ,. .. , N k in G such that G can be embedded into a graph H ∈ G such that for every edge e in H which is not an edge in G, there exists an i such that both endvertices of e are in N i. For the class B of block graphs we show that graphs with B-width at most 4 are perfect. We also show that B-width is NP-complete and show that it is fixed-parameter tractable. For the class C of complete graphs, similar results are also obtained.

A Graph G = (V, E) is called k-slim if for every subgraph S = (V S , E S) of G with s = |V S | ≥ k there exists K ⊂ V S , |K| = k, such that the vertices of V S \ K can be partitioned into two subsets, A and B, such that |A| ≤ 2 3 s and |B| ≤ 2 3 s and no edge of E S connects a vertex from A and a vertex from B. k-slim graphs contain, in particular, the graphs with tree-width k. In this paper we give an algorithm solving the H-decomposition problem for a large family of graphs H which contains, among others, the stars, the complete graphs, and the complete r-partite graphs where r ≥ 3. The algorithm runs in polynomial time in case the input graph is k-slim, where k is fixed. In particular, our algorithm runs in polynomial time when the input graph has bounded tree width k. Our results supply the first polynomial time algorithm for H-decomposition of connected graphs H having at least 3 edges, in graphs with bounded tree-width. 1 Introduction All graphs considered here are finite, undirected and simple. For the standard graph-theoretic notations the reader is referred to [5]. Let G = (V, E) be a graph, and let 0.5 < α < 1. A partition of V into three subsets K, A, B is called a (k, α)-separator if |K| = k and no edge of E connects a vertex from A and a vertex from B. Furthermore, |A| ≤ α|V | and |B| ≤ α|V |. Small separators of graphs have been studied extensively, see e.g. [11, 2]. We define the class of (k, α)-slim graphs, which are graphs G that have the property that every subgraph of G with more than k vertices has a (k, α)-separator. It is easy to see that every (k, α)slim graph is also a (dk, 2 3)-slim graph where d = max{1, log 2/3 log α }. Since in our applications k and α will be fixed, we only consider (k, 2 3)-slim graphs, and call them k-slim. By a k-separator we always mean a (k, 2/3)-separator. Note also that a k-slim graph does not have a 3k-connected subgraph, since such a subgraph must contain at least 3k + 1 vertices, and hence cannot have a k-separator.

Given a connected outerplanar graph G of pathwidth p, we give an algorithm to add edges to G to get a supergraph of G, which is 2-vertex-connected, outerplanar and of pathwidth O(p). This settles an open problem raised by Biedl [1], in the context of computing minimum height planar straight line drawings of outerplanar graphs, with their vertices placed on a two dimensional grid. In conjunction with the result of this paper, the constant factor approximation algorithm for this problem obtained by Biedl [1] for 2-vertex-connected outerplanar graphs will work for all outer planar graphs.

We describe algorithms for finding shortest paths and distances in a planar digraph which exploit the particular topology of the input graph. We give both sequential and parallel algorithms that work on a dynamic environment, where the cost of any edge can be changed or the edge can be deleted. For outerplanar digraphs, for instance, the data structures can be updated after any such change in only O(log n) time, where n is the number of vertices of the digraph. The parallel algorithms presented here are the first known ones for solving this problem. Our results can be extended to hold for digraphs of genus o(n).

We aimed to determine the usual intake of total fat, fatty acids (FAs), and their main food sources in a representative cohort of the Spanish pediatric population aged 1 to &lt;10 years (n = 707) who consumed all types of milk and an age-matched cohort who consumed adapted milk over the last year (including follow-on formula, toddler’s milk, growing-up milk, and fortified and enriched milks) (n = 741) who were participants in the EsNuPI study (in English, Nutritional Study in the Spanish Pediatric Population). Dietary intake, measured through two 24 h dietary recalls, was compared to the European Food Safety Authority (EFSA) and the Food and Agriculture Organization of the United Nations (UN-FAO) recommendations. Both cohorts showed a high intake of saturated fatty acids (SFAs), according to FAO recommendations, as there are no numerical recommendations for SFAs at EFSA. Also, low intake of essential fatty acids (EFAs; linoleic acid (LA) and α-linolenic acid (ALA)) and long-chain po...

It is shown that a static dictionary that offers constant-time access to n elements with w-bit keys and occupies O(n) words of memory can be constructed deterministically in O(n log n) time on a unit-cost RAM with word length w and a standard instruction set including multiplication. Whereas a randomized construction working in linear expected time was known, the running time of the best previous deterministic algorithm was Ω(n 2). Using a standard dynamization technique, the first deterministic dynamic dictionary with constant lookup time and sublinear update time is derived. The new algorithms are weakly nonuniform; i.e., they require access to a fixed number of precomputed constants dependent on w. The main technical tools employed are unit-cost error-correcting codes, word parallelism, and derandomization using conditional expectations.

On sparse graphs, Roditty and Williams [2013] proved that no O(n2−ε)- time algorithm achieves an approximation factor smaller than 3/2 for the diameter problem unless SETH fails. In this article, we solve an open question formulated in the literature: can we use the structural properties of median graphs to break this global quadratic barrier? We propose the first combinatiorial algorithm computing exactly all eccentricities of a median graph in truly subquadratic time. Median graphs constitute the family of graphs which is the most studied in metric graph theory because their structure represents many other discrete and geometric concepts, such as CAT(0) cube complexes. Our result generalizes a recent one, stating that there is a linear-time algorithm for all eccentricities in median graphs with bounded dimension d, i.e. the dimension of the largest induced hypercube. This prerequisite on d is not necessarily anymore to determine all eccentricities in subquadratic time. The executi...

Dynamic programming is widely used for exact computations based on tree decompositions of graphs. However, the space complexity is usually exponential in the treewidth. We study the problem of designing efficient dynamic programming algorithms based on tree decompositions in polynomial space. We show how to use a tree decomposition and extend the algebraic techniques of Lokshtanov and Nederlof (In: 42nd ACM Symposium on Theory of Computing, pp. 321-330, 2010) such that a typical dynamic programming algorithm runs in time O * (2 h), where h is the treedepth (Nešetřil et al., Eur. J. Comb. 27(6):1022-1041, 2006) of a graph. In general, we assume that a tree decomposition of depth h is given. We apply our algorithm to the problem of counting perfect matchings on grids and show that it outperforms other polynomial-space solutions. We also apply the algorithm to other set covering and partitioning problems.

The use of general descriptive names, registered names, trademarks, service marks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use.

One of the fundamental tasks in any distributed computing system is routing messages between pairs of nodes. An Interval Routing Scheme (IRS) is a space efficient way of routing messages in a network. The problem of characterizing graphs that support an IRS is a well-known problem and has been studied for some variants of IRS. It is natural to assume that the costs of links may vary over time (dynamic cost links) and to try to find an IRS which routes all messages on shortest paths (optimum IRS). In this paper, we study this problem for a variant of IRS in which the labels assigned to the vertices are d-ary integer tuples (d-dimensional IRS). The only known results in this case are for specific graphs like hypercubes, n-dimensional grids, or for the 1-dimensional case. We give a complete characterization for the class of networks supporting multi-dimensional strict and linear (which is a variation of IRS) interval routing schemes with dynamic cost links.

In this paper, we i n vestigate which processor networks allow klabel Interval Routing Schemes, under the assumption that costs of edges may v ary. We show that for each xed k 1, the class of graphs allowing such routing schemes is closed under minor-taking in the domain of connected graphs, and hence has a linear time recognition algorithm. This result connects the theory of compact routing with the theory of graph minors and treewidth. We show that every graph that does not contain K 2;r as a minor has treewidth at most 2r , 2. In case the graph is planar, this bound can belowered to r + 2. As a consequence, graphs that allow k-label Interval Routing Schemes under dynamic cost edges have treewidth at most 4k, and treewidth at most 2k + 3 if they are planar. Similar results are shown for other types of Interval Routing Schemes.

We give a polynomial time algorithm to compute the bandwidth of a (q; q − 4)-graph for each constant q. We show also that the bandwidth and topological bandwidth of P4-sparse graphs are equal. Let H be a subdivision of a graph G with a minimal number of vertices such that the bandwidth of H equals the topological bandwidth of G. We show that the number of vertices of H is O(n 3), where n is the number of vertices in G, and thus the topological bandwidth of a graph of constant size can be computed in constant time. ? 2001 Published by Elsevier Science B.V.

We consider the following problem: given graph G and a set of graphs H = {H1,. .. , Ht}, what is the smallest subset S of edges in G such that all subgraphs of G that are isomorphic to one of the graphs from H contain at least one edge from S? Equivalently, we aim to find the minimum number of edges that needs to be removed from G to make it H-free. We concentrate on the case where all graphs Hi are connected and have fixed size. Several algorithmic results are presented. First, we derive a polynomial time dynamic program for the problem on graphs of bounded treewidth and bounded maximum vertex degree. Then, if H contains only a clique, we adjust the dynamic program to solve the problem on graphs of bounded treewidth having arbitrary maximum vertex degree. Using the constructed dynamic programs, we design a Baker's type approximation scheme for the problem on planar graphs. Finally, we observe that our results hold also if we cover only induced H-subgraphs.

A graph that changes with time is called a temporal graph. In this work, we focus on temporal graphs whose vertex sets are fixed while edge sets change in discrete time steps. We use n to refer to the number of vertices in the graph and τ to refer to the total number of time steps over which a temporal graph is observed. We refer to non-temporal graphs as static graphs when we wish to emphasize their unchanging nature. In this work, we study temporal analogues of the Vertex Separator and Vertex Cover problems from the static world with an emphasis on the Vertex Separator problem. An (s,z)-temporal separator is a set of vertices whose removal disconnects vertex s from vertex z for every time step in a temporal graph. The (s,z)-Temporal Separator problem asks to find the minimum size of an (s,z)-temporal separator for the given temporal graph. The (s,z)-Temporal Separator problem is known to be NP-hard in general, although some special cases (such as bounded treewidth) admit efficient...

ont montré que tout arbre à n noeuds possède un schéma de routage de plus courts chemins utilisant des adresses, des en-têtes et des tables de routage de O(log n) bits. Il est ouvert de savoir si ce résultat optimal peut être étendu, ne serait-ce qu'aux réseaux de largeur arborescente deux dont la meilleure borne connue, due à (Peleg, 2000) est O(log 2 n) bits. Dans cet article, nous étendons ce résultat optimal aux réseaux appelés (k, r)-constellations, c'est-à-dire aux réseaux ne contenant pas K2,r comme mineur et dont les composantes bi-connexes peuvent être rendues planaire-extérieures par la suppression de k sommets. Par exemple, les (2, 4)-constellations contiennent les arbres, les graphes planaire-extérieurs et plus généralement les graphes sans mineur K2,4. ABSTRACT. (Fraigniaud et al., 2001) and independently (Thorup et al., 2001) show that n-node trees support routing schemes with message headers, node addresses, and routing tables of O(log n) bits. It still open to known if this optimal result can be extended to the tree-width two graphs. The best known routing scheme require O(log 2 n) bits (cf. (Peleg, 2000)). In this article, we extend this optimal result to (k, r)-constellations, i.e., K2,r-minor free networks whose bi-connected components are outerplanar by deleting k vertices. For example, (2, 4)constellations contain trees, outerplanars and more generally all K2,4-minor free networks.

A graph G = (V, E) is called (k, ℓ)-full if G contains a subgraph H = (V, F) of k|V | − ℓ edges such that, for any non-empty F ′ ⊆ F , |F ′ | ≤ k|V (F ′)| − ℓ holds. Here, V (F ′) denotes the set of vertices incident to F ′. It is known that the family of edge sets of (k, ℓ)-full graphs forms a family of matroid, known as the sparsity matroid of G. In this paper, we give a constant-time approximation algorithm for the rank of the sparsity matroid of a degree-bounded undirected graph. This leads to a constant-time tester for (k, ℓ)-fullness in the bounded-degree model, (i.e., we can decide with high probability whether an input graph satisfies a property P or far from P). Depending on the values of k and ℓ, it can test various properties of a graph such as connectivity, rigidity, and how many spanning trees can be packed. Based on this result, we also propose a constant-time tester for (k, ℓ)-edge-connected-orientability in the bounded-degree model, where an undirected graph G is called (k, ℓ)-edge-connectedorientable if there exists an orientation G of G with a vertex r ∈ V such that G contains k arc-disjoint dipaths from r to each vertex v ∈ V and ℓ arc-disjoint dipaths from each vertex v ∈ V to r. A tester is called a one-sided error tester for P if it always accepts a graph satisfying P. We show, for k ≥ 2 and (proper) ℓ ≥ 0, any one-sided error tester for (k, ℓ)-fullness and (k, ℓ)-edgeconnected-orientability requires Ω(n) queries.

Large scale graph processing using distributed computing frameworks is becoming pervasive and efficient in the industry. In this work, we present a highly scalable and configurable distributed algorithm for building connected components, called Union Find Shuffle (UFS) with Path Compression. The scale and complexity of the algorithm are a function of the number of partitions into which the data is initially partitioned, and the size of the connected components. We discuss the complexity and the benchmarks compared to similar approaches. We also present current benchmarks of our production system, running on commodity out-of-the-box cloud Hadoop infrastructure, where the algorithm was deployed over a year ago, scaled to around 75 Billion nodes and 60 Billions linkages (and growing). We highlight the key aspects of our algorithm which enable seamless scaling and performance even in the presence of skewed data with large connected components in the size of 10 Billion nodes each.

Ever-increasing demands for portable and flexible communications have led to rapid growth in networking between unmanned aerial vehicles often referred to as flying ad-hoc networks (FANETs). Existing mobile ad hoc routing protocols are not suitable for FANETs due to high-speed mobility, environmental conditions, and terrain structures. In order to overcome such obstacles, we propose a combined omnidirectional and directional transmission scheme, together with dynamic angle adjustment. Our proposed scheme features hybrid use of unicasting and geocasting routing using location and trajectory information. The prediction of intermediate node location using 3-D estimation and directional transmission toward the predicted location, enabling a longer transmission range, allows keeping track of a changing topology, which ensures the robustness of our protocol. In addition, the reduction in path re-establishment and service disruption time to increase the path lifetime and successful packet transmissions ensures the reliability of our proposed strategy. Simulation results verify that our proposed scheme could significantly increase the performance of flying ad hoc networks. INDEX TERMS FANET, routing protocol, directional transmission, route setup, average path lifetime, dynamic angle adjustment.

DOI to the publisher's website. • The final author version and the galley proof are versions of the publication after peer review. • The final published version features the final layout of the paper including the volume, issue and page numbers. Link to publication General rights Copyright and moral rights for the publications made accessible in the public portal are retained by the authors and/or other copyright owners and it is a condition of accessing publications that users recognise and abide by the legal requirements associated with these rights. • Users may download and print one copy of any publication from the public portal for the purpose of private study or research. • You may not further distribute the material or use it for any profit-making activity or commercial gain • You may freely distribute the URL identifying the publication in the public portal.

In a large dynamic network, data can be copied anywhere to make it fault tolerant and easy accessed but there must be an efficient protocol to manage the replicas and make sure the data is consistent and high in availability with a low communication cost. In this paper, we introduced a new protocol, named Diagonal Replication in Mesh (DRM) for data replica control protocol for a large dynamic network by using quorum and voting techniques to improve the availability and the communication cost because quorum techniques reduce the number of copies involved in reading or writing data.The protocol of DRM replicates data for large dynamic network by putting the protocol in a logical mesh structure and access consistent data by ensuring the quorum not to have a nonempty intersection quorum.To evaluate our protocol, we developed a simulation model in Java.Our results proved that DRM improves the performance of the response time compare to Three Dimensional Grid structure Protocol (TDGS).

In distributed graph algorithms, a key computational resource is the communication radius of the algorithm, i.e., its locality. The class LD captures the distributed languages that can be decided by a local algorithm; its nondeterministic analog is the class NLD, which captures the distributed languages that can be decided by a local algorithm with local advice. Inspired by the polynomial hierarchy in complexity theory, this has been further extended into a hierarchy of local decision, where each node runs an alternating Turing machine. However, in prior work, the computational efficiency of each network node as nodes where allowed to run Turing machines for unbounded number of steps. This results in some undesirable and unanticipated properties: for example, the class NLD includes some Turing-undecidable languages. In this brief announcement we study a version of local decision where nodes are restricted to polynomial-time computation, and define a polynomial-time local decision hierarchy. At the base of the hierarchy is the class LD , of all distributed languages that can be decided by local algorithms that are also computationally efficient. We show that requiring one algorithm that is both local and computationally efficient is more restrictive than requiring each separately, that is, LD ⊊ LD ∩ P. This separation persists into the first level of the hierarchy, but disappears starting from the second level. We also show that if the polynomial-time local decision hierarchy is not strict, then this implies a collapse of the sequential polynomial hierarchy. CCS CONCEPTS • Theory of computation → Complexity classes; Computability.

We introduce the following notion of compressing an undirected graph G with (nonnegative) edge-lengths and terminal vertices R ⊆ V (G). A distance-preserving minor is a minor G ′ (of G) with possibly different edge-lengths, such that R ⊆ V (G ′) and the shortest-path distance between every pair of terminals is exactly the same in G and in G ′. We ask: what is the smallest f * (k) such that every graph G with k = |R| terminals admits a distance-preserving minor G ′ with at most f * (k) vertices? Simple analysis shows that f * (k) ≤ O(k 4). Our main result proves that f * (k) ≥ Ω(k 2), significantly improving over the trivial f * (k) ≥ k. Our lower bound holds even for planar graphs G, in contrast to graphs G of constant treewidth, for which we prove that O(k) vertices suffice.

We introduce the following notion of compressing an undirected graph G with (nonnegative) edge-lengths and terminal vertices R ⊆ V (G). A distance-preserving minor is a minor G ′ (of G) with possibly different edge-lengths, such that R ⊆ V (G ′) and the shortest-path distance between every pair of terminals is exactly the same in G and in G ′. We ask: what is the smallest f * (k) such that every graph G with k = |R| terminals admits a distance-preserving minor G ′ with at most f * (k) vertices? Simple analysis shows that f * (k) ≤ O(k 4). Our main result proves that f * (k) ≥ Ω(k 2), significantly improving over the trivial f * (k) ≥ k. Our lower bound holds even for planar graphs G, in contrast to graphs G of constant treewidth, for which we prove that O(k) vertices suffice.

The problem offinding a minimum-weight k-connected spanning subgraph ofa complete graph, assuming that the edge weights satisfy the triangle inequality, is studied. It is shown that the class of minimumweight k-edge connected spanning subgraphs can be restricted to those subgraphs which, in addition to the connectivity requirements, satisfy the following two conditions: (I) Every vertex has degree k or k + 1; (II) Removing any l, 2, ..-, or k edges does not leave the resulting connected components all k-edge connected. For the k-vertex connected case, the parallel result is obtained with "k-edge" replaced by "k-vertex," with the added technical restriction that V >= 2k for condition (I) to hold. This generalizes recent work of Monma, Munson, and Pulleyblank for the case k 2. Key words, survivability, graph theory, lifting, connectivity AMS(MOS) subject classifications. 05C40, 94C 15, 90C35 1. Introduction. In the design of communication or transportation networks, it is frequently important to produce networks of low "cost" which are also "survivable." In many cases the cost arises, to a good degree of approximation, in the form ofedge weights that satisfy the "triangle inequality" (defined in precise form below). The overall cost, or weight, or a network is the sum of the individual edge weights. For survivability reasons, the network must satisfy certain connectivity requirements (see [CW], [GM], [MS], [SWK] for more motivation). A typical survivability requirement is that the removal of any (k or fewer edges (or vertices) leaves the remaining network connected. The following standard definitions are required to make the above statements precise. A graph or network G (V, E) is called k-edge connected if the removal of any (k or fewer edges leaves G connected. If, in addition, the removal of any (k or fewer vertices leaves the remaining vertices of G connected, then G is called k-vertex connected. We note that the degenerate graph consisting of a single vertex is k-edge and k-vertex connected for all values of k. A variation of Menger's Theorem states that a nondegenerate graph G is k-edge (respectively, k-vertex) connected if and only if there are k edge (respectively, vertex) disjoint paths between every pair of vertices in G. Hence we obtain the following problem, k-connected network design with triangle inequality: given a complete graph with edge weights that satisfy the triangle inequality, and an integer k, find a minimum-weight k-edge (or k-vertex) connected spanning subgraph. We remark that for any k >_-2 this problem is NP-Hard, as the Hamiltonian Cycle problem can be reduced to a 2-connected network design problem with triangle inequality. Further, in general there will be a difference between the "edge-connected" and "vertex-connected" versions of this problem. In the following, the word "spanning" will be omitted, for convenience. A solution will be a k-connected subgraph. An optimal subgraph or solution will be a solution of least total weight. This paper presents some strong structural properties that optimal subgraphs can be assumed to satisfy. In particular, our results show that there are optimal subgraphs

Efficient parallel algorithms are presented, on the CREW PRAM model, for generating a succinct encoding of all pairs shortest path information in a directed planar graph G with real-valued edge costs but no negative cycles. We assume that a planar embedding of G is given, togetber with a set of q faces that cover all the vertices. Then our algorithm runs in O(log 2 n) time and employs O{nq + M(q)) processors (where M(t) is the number of processors required to multiply two t x t matrices in O(log t) time). Let us note here that whenever q < n then our processor bound is better than the best previous one (M(n)). O(log 2 n) time, n-processor algorithms are presented for various subproblems, including that of generating all pairs shortest path information in a directed outerplanar graph. Our work is based on the fundamental hammock-decomposition technique ofG. Frederickson. We achieve this decomposition in O(log n log* n) parallel time by using O(n) processors. The hammock-decomposition seems to be a fundamental operation that may help in improving efficiency of many parallel (and sequential) graph algorithms.

Interval Routing is a routing method that was proposed in order to reduce the size of the routing tables by using intervals and was extensively studied and implemented. Some variants of the original method were also deÿned and studied. The question of characterizing networks which support optimal (i.e., shortest path) Interval Routing has been thoroughly investigated for each of the variants and under di erent models, with only partial answers, both positive and negative, given so far. In this paper, we study the characterization problem under the most basic model (the one unit cost), and with the most restrictive memory requirements (one interval per edge). We prove that this problem is NP-hard (even for the restricted class of graphs of diameter at most 3). Our result holds for all variants of Interval Routing. It signiÿcantly extends some related NP-hardness result, and implies that, unless P = NP, partial characterization results of some classes of networks which support shortest path Interval Routing, cannot be pushed further to lead to e cient characterizations for these classes.

We introduce the new Masked Interval Routing Scheme, MIRS for short, where a mask is added to each interval to indicate particular subsets of "consecutive" labels. Interval routing becomes more exible, with the classical IRS scheme being a special case of MIRS. We then take two directions. First we show that the interval information stored in the network may be drastically reduced in the hard cases, proving that in globe graphs of O(n 2) vertices the number of intervals per edge goes down from (n) to O(log n). The technique is then extended to globe graphs of arbitrary dimensions. Second we show that MIRS may be advantageously used in fault-tolerant networks, proving that optimal routing with one interval per edge is still possible in hypercubes with a "harmless" subset of faulty vertices. This work is aimed to introducing a new technique. Further research is needed in both the directions taken here. Still, the examples provided show that MIRS may be useful in practical applications.

Shortest paths in weighted directed graphs are considered within the context of compact routing tables. Strategies are given for organizing compact routing tables so that extracting a requested shortest path will take o(k logn) time, where k is the number of edges in the path and n is the number of vertices in the graph. The first strategy takes O (k + log n) time to extract a requested shortest path. A second strategy takes O(k) time on average, assuming all n(n-1) shortest paths are equally likely to be requested. Both strategies introduce techniques for storing collections of disjoint intervals over the integers from 1 to n, so that identifying the interval within which a given integer falls can be performed quickly.

An algorithm is presented for generating a succinct encoding of all pairs shortest path information in a directed planar graph G with real-valued edge costs but no negative cycles. The algorithm runs in O ( pn ) time, where n is the number of vertices in G , and p is the minimum cardinality of a subset of the faces that cover all vertices, taken over all planar embeddings of G . The algorithm is based on a decomposition of the graph into O ( pn ) outerplanar subgraphs satisfying certain separator properties. Linear-time algorithms are presented for various subproblems including that of finding an appropriate embedding of G and a corresponding face-on-vertex covering of cardinality O ( p ), and of generating all pairs shortest path information in a directed outerplannar graph.

The paper describes two relatively simple modifications of the well-known Floyd-Warshall algorithm for computing all-pairs shortest paths. A fundamental difference of both modifications in comparison to the Floyd-Warshall algorithm is that the relaxation is done in a smart way. We show that the expected-case time complexity of both algorithms is O(n 2 log 2 n) for the class of complete directed graphs on n vertices with arc weights selected independently at random from the uniform distribution on [0, 1]. Theoretically best known algorithms for this class of graphs are all based on Dijkstra's algorithm and obtain a better expected-case bound. However, by conducting an empirical evaluation we prove that our algorithms are at least competitive in practice with best know algorithms and, moreover, outperform most of them. The reason for the practical efficiency of the presented algorithms is the absence of use of priority queue. * A preliminary version of this work has been published in Shortest Path Solvers: From Software to Wetware, volume 32 of Emergence, Complexity and Computation (2018). The authors would like to thank the reviewer for excellent comments that substantially improved the quality of the paper.

The paper describes two relatively simple modifications of the well-known Floyd-Warshall algorithm for computing all-pairs shortest paths. A fundamental difference of both modifications in comparison to the Floyd-Warshall algorithm is that the relaxation is done in a smart way. We show that the expected-case time complexity of both algorithms is O(n 2 log 2 n) for the class of complete directed graphs on n vertices with arc weights selected independently at random from the uniform distribution on [0, 1]. Theoretically best known algorithms for this class of graphs are all based on Dijkstra's algorithm and obtain a better expected-case bound. However, by conducting an empirical evaluation we prove that our algorithms are at least competitive in practice with best know algorithms and, moreover, outperform most of them. The reason for the practical efficiency of the presented algorithms is the absence of use of priority queue. * A preliminary version of this work has been published in Shortest Path Solvers: From Software to Wetware, volume 32 of Emergence, Complexity and Computation (2018). The authors would like to thank the reviewer for excellent comments that substantially improved the quality of the paper.

The paper describes two relatively simple modifications of the well-known Floyd-Warshall algorithm for computing all-pairs shortest paths. A fundamental difference of both modifications in comparison to the Floyd-Warshall algorithm is that the relaxation is done in a smart way. We show that the expected-case time complexity of both algorithms is O(n 2 log 2 n) for the class of complete directed graphs on n vertices with arc weights selected independently at random from the uniform distribution on [0, 1]. Theoretically best known algorithms for this class of graphs are all based on Dijkstra's algorithm and obtain a better expected-case bound. However, by conducting an empirical evaluation we prove that our algorithms are at least competitive in practice with best know algorithms and, moreover, outperform most of them. The reason for the practical efficiency of the presented algorithms is the absence of use of priority queue. * A preliminary version of this work has been published in Shortest Path Solvers: From Software to Wetware, volume 32 of Emergence, Complexity and Computation (2018). The authors would like to thank the reviewer for excellent comments that substantially improved the quality of the paper.

Alquran adalah sumber ilmu pengetahuan yang pertama dan utama. Sebagai wahyu, ia mempunyai fungsi sebagai kitab petunjuk ( hudan ) dan rahmat bagi seluruh alam. Dengan demikian, Alquran mengandung nilai-nilai, sistem, dan tata cara dan pandangan hidup ( the way of life ). Tidak hanya masalah akidah, ibadah, dan muamalah yang diatur di dalamnya. Masalah-masalah sosial, politik, budaya, ekonomi, dan pembentukan kepribadian yang agung juga diatur, termasuk di dalamnya tentang pendidikan. Dalam Alquran ditemukan banyak istilah yang berkaitan dengan pendidikan. Beragam istilah atau term itu, antara lain, ta&#39;lȋm, tarbiyah, tazkiyah, irsyâd , dan lain sebagainya. Penelitian ini ditulis dengan metodologi bayânȋ , dengan pendekatan metode tafsir maudlu’ȋ, atau deskriptif filosofis

A graph G is δ-hyperbolic if for any four vertices u, v, x, y of G the two larger of the three distance sums dG(u, v) + dG(x, y), dG(u, x) + dG(v, y), dG(u, y) + dG(v, x) differ by at most δ, and the smallest δ 0 for which G is δ-hyperbolic is called the hyperbolicity of G. In this paper, we construct a distance labeling scheme for bounded hyperbolicity graphs, that is a vertex labeling such that the distance between any two vertices of G can be estimated from their labels, without any other source of information. More precisely, our scheme assigns labels of O(log 2 n) bits for bounded hyperbolicity graphs with n vertices such that distances can be approximated within an additive error of O(log n). The label length is optimal for every additive error up to n ε . We also show a lower bound of Ω(log log n) on the approximation factor, namely every s-multiplicative approximate distance labeling scheme on bounded hyperbolicity graphs with polylogarithmic labels requires s = Ω(log log n).

We consider the problem of finding a short path between any two nodes of a network when no global information is available, nor any oracle to help in routing. A mobile agent, situated in a starting node, has to walk to a target node traversing a path of minimum length. All information about adjacencies is distributed to the nodes, with certain nodes (called landmarks) storing more information in order to describe a neighboring subgraph associated with each of them. We wish to minimize the total memory requirements as well as keep the memory requirements per landmark to reasonable levels. We propose a landmark selection and information distribution scheme with overall memory requirement linear in the number of nodes, and constant memory consumption per nonlandmark node. We prove that a navigation algorithm using this scheme attains a constant stretch factor overhead in tree topologies, compared to an optimal landmark-based routing algorithm that obeys certain restrictions. The flexibility of our approach allows for various trade-offs, such as between the number of landmarks and the size of the region assigned to each landmark.