The Experts below are selected from a list of 297 Experts worldwide ranked by ideXlab platform
Keiichi Kaneko - One of the best experts on this subject based on the ideXlab platform.
-
Pairwise Disjoint Paths Routing in Tori
IEEE Access, 2020Co-Authors: Keiichi Kaneko, Son Van Nguyen, Hyunh Thi Thanh BinhAbstract:The Pairwise Disjoint paths problem is to construct $c$ Disjoint paths $\boldsymbol {s} _{i}\leadsto \boldsymbol {d} _{i}$ ( $1\le i\le c$ ) between given pairs of nodes $(\boldsymbol {s} _{i}, \boldsymbol {d} _{i})$ ( $1\le i\le c$ ) in a graph whose connectivity is no less than $2c$ . It is a major problem for interconnection networks, together with the node-to-node Disjoint paths problem, the node-to-set Disjoint paths problem, and the set-to-set Disjoint paths problem. In this paper, we propose an algorithm that solves this problem for a torus. In a previous work, Bossard and Kaneko have developed an algorithm that constructs Disjoint paths between $c$ pairs of nodes in a $k$ -ary $n$ -dimensional torus, where $c\le n$ . The time complexity of their algorithm is $O(c^{4}n+kcn)$ , and the maximum path length is $\lfloor k/2\rfloor n+2k(c-1)$ . However, the algorithm proposed in this paper achieves a time complexity of $O(c^{3}n+kcn)$ , and its maximum path length is $\lfloor k/2\rfloor n+(\lceil 3k/2\rceil -2)(c-1)$ , which are both improvements over the previous algorithm. We also conducted an evaluation experiment to show that the average path lengths are proportional to $k$ if $n$ is fixed, and to $n$ if $k$ is fixed. The theoretical maximum path lengths were not attained by the paths constructed by our algorithm, and the average execution time was proportional to $k$ if $n$ is fixed, and to $n^{2}$ if $k$ is fixed. Additional experimental results show that, compared to the previous algorithm by Bossard and Kaneko, our algorithm achieves a better performance with respect to the maximum path lengths, but both algorithms achieve a similar level of performance with respect to the average maximum path lengths. Also, it is shown that the average execution time of our algorithm is about $O(n^{2})$ , which is better than the average execution time of the previous algorithm $O(n^{3})$ in the experimental framework.
-
Torus Pairwise Disjoint-Path Routing.
Sensors (Basel Switzerland), 2018Co-Authors: Antoine Bossard, Keiichi KanekoAbstract:Modern supercomputers include hundreds of thousands of processors and they are thus massively parallel systems. The interconnection network of a system is in charge of mutually connecting these processors. Recently, the torus has become a very popular interconnection network topology. For example, the Fujitsu K, IBM Blue Gene/L, IBM Blue Gene/P, and Cray Titan supercomputers all rely on this topology. The Pairwise Disjoint-path routing problem in a torus network is addressed in this paper. This fundamental problem consists of the selection of mutually vertex Disjoint paths between given vertex pairs. Proposing a solution to this problem has critical implications, such as increased system dependability and more efficient data transfers, and provides concrete implementation of green and sustainable computing as well as security, privacy, and trust, for instance, for the Internet of Things (IoT). Then, the correctness and complexities of the proposed routing algorithm are formally established. Precisely, in an n-dimensional k-ary torus ( n < k , k ≥ 5 ), the proposed algorithm connects c ( c ≤ n ) vertex pairs with mutually vertex-Disjoint paths of lengths at most 2 k ( c - 1 ) + n ⌊ k / 2 ⌋ , and the worst-case time complexity of the algorithm is O ( n c 4 ) . Finally, empirical evaluation of the proposed algorithm is conducted in order to inspect its practical behavior.
-
on the torus Pairwise Disjoint path routing problem
Green Computing and Communications, 2018Co-Authors: Antoine Bossard, Keiichi KanekoAbstract:Modern supercomputers are massively parallel systems: they include hundreds of thousands of processors. Processor connection is realised by the interconnection network of the system. In recent years, the torus topology has proven very popular as interconnection network: the Fujitsu K, IBM Blue Gene/L, IBM Blue Gene/P and Cray Titan supercomputers are examples of devices relying on this topology. In this paper, we address the fundamental problem of Pairwise Disjoint-path routing in a torus network. This problem is about selecting mutually node Disjoint paths between given node pairs. Solving this problem has very important implications such as increased system dependability and more efficient data transfers. The correctness and complexities of the proposed routing algorithm to solve this problem are formally established. In an n-dimensional k-ary torus (n $c$ (≤ n) node pairs with mutually node Disjoint paths of lengths at most 2k(c - 1) + n [k / 2], and the worst-case time complexity of the algorithm is O (nk2c3).
-
iThings/GreenCom/CPSCom/SmartData - On the Torus Pairwise Disjoint-Path Routing Problem
2018 IEEE International Conference on Internet of Things (iThings) and IEEE Green Computing and Communications (GreenCom) and IEEE Cyber Physical and , 2018Co-Authors: Antoine Bossard, Keiichi KanekoAbstract:Modern supercomputers are massively parallel systems: they include hundreds of thousands of processors. Processor connection is realised by the interconnection network of the system. In recent years, the torus topology has proven very popular as interconnection network: the Fujitsu K, IBM Blue Gene/L, IBM Blue Gene/P and Cray Titan supercomputers are examples of devices relying on this topology. In this paper, we address the fundamental problem of Pairwise Disjoint-path routing in a torus network. This problem is about selecting mutually node Disjoint paths between given node pairs. Solving this problem has very important implications such as increased system dependability and more efficient data transfers. The correctness and complexities of the proposed routing algorithm to solve this problem are formally established. In an n-dimensional k-ary torus (n $c$ (≤ n) node pairs with mutually node Disjoint paths of lengths at most 2k(c - 1) + n [k / 2], and the worst-case time complexity of the algorithm is O (nk2c3).
-
k-Pairwise Disjoint paths routing in perfect hierarchical hypercubes
The Journal of Supercomputing, 2013Co-Authors: Antoine Bossard, Keiichi KanekoAbstract:Hierarchical hypercubes (HHC), also known as cube-connected cubes, have been introduced in the literature as an interconnection network for massively parallel systems. Effectively, they can connect a large number of nodes while retaining a small diameter and a low degree compared to a hypercube of the same size. Especially (2 m +m)-dimensional hierarchical hypercubes ( $\mathit {HHC}_{2^{m}+m}$ ), called perfect HHCs, are popular as they are symmetrical, which is a critical property when designing routing algorithms. In this paper, we describe an algorithm finding, in an $\mathit{HHC}_{2^{m}+m}$ , mutually node-Disjoint paths connecting k=?(m+1)/2? pairs of distinct nodes. This problem is known as the k-Pairwise Disjoint-path routing problem and is one of the important routing problems when dealing with interconnection networks. In an $\mathit{HHC}_{2^{m}+m}$ , our algorithm finds paths of lengths at most 2 m+1+m(2 m+1+1)+4 in O(25m ) time, where 2 m+1 is the diameter of an $\mathit{HHC}_{2^{m}+m}$ . Also, we have shown through an experiment that, in practice, the lengths of the generated paths are significantly lower than the worst-case theoretical estimations.
Rephael Wenger - One of the best experts on this subject based on the ideXlab platform.
-
Constructing Pairwise Disjoint paths with few links
ACM Transactions on Algorithms, 2007Co-Authors: Himanshu Gupta, Rephael WengerAbstract:Let P be a simple polygon and let {(u1, u′1), (u2, u′2),…,(um, u′m)} be a set of m pairs of distinct vertices of P, where for every distinct i, j ≤ m, there exist Pairwise Disjoint (nonintersecting) paths connecting ui to u′i and uj to u′j. We wish to construct m Pairwise Disjoint paths in the interior of P connecting ui to u′i for i e 1, …,m, with a minimal total number of line segments. We give an approximation algorithm that constructs such a set of paths using O(M) line segments in O(n log m p M log m) time, where M is the number of line segments in the optimal solution and n is the size of the polygon.
-
constructing Pairwise Disjoint paths with few links
Workshop on Algorithms and Data Structures, 1997Co-Authors: Himanshu Gupta, Rephael WengerAbstract:Let P be a simple polygon and let {(ui,u i ′ )} be m pairs of distinct vertices of P where for every distinct i, j ≤ m, there exist Pairwise Disjoint paths connecting u i to u i ′ and u j to u j . We wish to construct m Pairwise Disjoint paths in the interior of P connecting u i to u i ′ for i = 1, ..., m, with minimal total number of line segments. We give an approximation algorithm which in O(n log m + M log m) time constructs such a set of paths using O(M) line segments where M is the number of line segments in the optimal solution.
-
WADS - Constructing Pairwise Disjoint Paths with Few Links
Lecture Notes in Computer Science, 1997Co-Authors: Himanshu Gupta, Rephael WengerAbstract:Let P be a simple polygon and let {(ui,u i ′ )} be m pairs of distinct vertices of P where for every distinct i, j ≤ m, there exist Pairwise Disjoint paths connecting u i to u i ′ and u j to u j . We wish to construct m Pairwise Disjoint paths in the interior of P connecting u i to u i ′ for i = 1, ..., m, with minimal total number of line segments. We give an approximation algorithm which in O(n log m + M log m) time constructs such a set of paths using O(M) line segments where M is the number of line segments in the optimal solution.
-
On the connected components of the space of line transversals to a family of convex sets
Discrete and Computational Geometry, 1995Co-Authors: Jacob E. Goodman, Ricky Pollack, Rephael WengerAbstract:Let ? be the space of line transversals to a finite family of Pairwise Disjoint compact convex sets in ?3. We prove that each connected component of ? can itself be represented as the space of transversals to some finite family of Pairwise Disjoint compact convex sets.
-
Ordered stabbing of Pairwise Disjoint convex in linear time
Discrete Applied Mathematics, 1991Co-Authors: Peter Egyed, Rephael WengerAbstract:Abstract Given an ordered family of n Pairwise Disjoint convex simple objects in the plane, we give an O( n ) time algorithm for finding the directed line transversals of the family that intersect the objects in order. Objects are simple if they have a constant size storage description, and if the intersections and common tangents between any two objects can be found in constant time. Our O( n ) time algorithm contrasts with an Ω( n log n ) lower bound for finding a line transversal of a family of n convex simple objects in the plane.
Hyunh Thi Thanh Binh - One of the best experts on this subject based on the ideXlab platform.
-
Pairwise Disjoint Paths Routing in Tori
IEEE Access, 2020Co-Authors: Keiichi Kaneko, Son Van Nguyen, Hyunh Thi Thanh BinhAbstract:The Pairwise Disjoint paths problem is to construct $c$ Disjoint paths $\boldsymbol {s} _{i}\leadsto \boldsymbol {d} _{i}$ ( $1\le i\le c$ ) between given pairs of nodes $(\boldsymbol {s} _{i}, \boldsymbol {d} _{i})$ ( $1\le i\le c$ ) in a graph whose connectivity is no less than $2c$ . It is a major problem for interconnection networks, together with the node-to-node Disjoint paths problem, the node-to-set Disjoint paths problem, and the set-to-set Disjoint paths problem. In this paper, we propose an algorithm that solves this problem for a torus. In a previous work, Bossard and Kaneko have developed an algorithm that constructs Disjoint paths between $c$ pairs of nodes in a $k$ -ary $n$ -dimensional torus, where $c\le n$ . The time complexity of their algorithm is $O(c^{4}n+kcn)$ , and the maximum path length is $\lfloor k/2\rfloor n+2k(c-1)$ . However, the algorithm proposed in this paper achieves a time complexity of $O(c^{3}n+kcn)$ , and its maximum path length is $\lfloor k/2\rfloor n+(\lceil 3k/2\rceil -2)(c-1)$ , which are both improvements over the previous algorithm. We also conducted an evaluation experiment to show that the average path lengths are proportional to $k$ if $n$ is fixed, and to $n$ if $k$ is fixed. The theoretical maximum path lengths were not attained by the paths constructed by our algorithm, and the average execution time was proportional to $k$ if $n$ is fixed, and to $n^{2}$ if $k$ is fixed. Additional experimental results show that, compared to the previous algorithm by Bossard and Kaneko, our algorithm achieves a better performance with respect to the maximum path lengths, but both algorithms achieve a similar level of performance with respect to the average maximum path lengths. Also, it is shown that the average execution time of our algorithm is about $O(n^{2})$ , which is better than the average execution time of the previous algorithm $O(n^{3})$ in the experimental framework.
Himanshu Gupta - One of the best experts on this subject based on the ideXlab platform.
-
Constructing Pairwise Disjoint paths with few links
ACM Transactions on Algorithms, 2007Co-Authors: Himanshu Gupta, Rephael WengerAbstract:Let P be a simple polygon and let {(u1, u′1), (u2, u′2),…,(um, u′m)} be a set of m pairs of distinct vertices of P, where for every distinct i, j ≤ m, there exist Pairwise Disjoint (nonintersecting) paths connecting ui to u′i and uj to u′j. We wish to construct m Pairwise Disjoint paths in the interior of P connecting ui to u′i for i e 1, …,m, with a minimal total number of line segments. We give an approximation algorithm that constructs such a set of paths using O(M) line segments in O(n log m p M log m) time, where M is the number of line segments in the optimal solution and n is the size of the polygon.
-
constructing Pairwise Disjoint paths with few links
Workshop on Algorithms and Data Structures, 1997Co-Authors: Himanshu Gupta, Rephael WengerAbstract:Let P be a simple polygon and let {(ui,u i ′ )} be m pairs of distinct vertices of P where for every distinct i, j ≤ m, there exist Pairwise Disjoint paths connecting u i to u i ′ and u j to u j . We wish to construct m Pairwise Disjoint paths in the interior of P connecting u i to u i ′ for i = 1, ..., m, with minimal total number of line segments. We give an approximation algorithm which in O(n log m + M log m) time constructs such a set of paths using O(M) line segments where M is the number of line segments in the optimal solution.
-
WADS - Constructing Pairwise Disjoint Paths with Few Links
Lecture Notes in Computer Science, 1997Co-Authors: Himanshu Gupta, Rephael WengerAbstract:Let P be a simple polygon and let {(ui,u i ′ )} be m pairs of distinct vertices of P where for every distinct i, j ≤ m, there exist Pairwise Disjoint paths connecting u i to u i ′ and u j to u j . We wish to construct m Pairwise Disjoint paths in the interior of P connecting u i to u i ′ for i = 1, ..., m, with minimal total number of line segments. We give an approximation algorithm which in O(n log m + M log m) time constructs such a set of paths using O(M) line segments where M is the number of line segments in the optimal solution.
Andrey Kupavskii - One of the best experts on this subject based on the ideXlab platform.
-
New inequalities for families without k Pairwise Disjoint members
Journal of Combinatorial Theory Series A, 2018Co-Authors: Peter Frankl, Andrey KupavskiiAbstract:Abstract Some best possible inequalities are established for k-partition-free families (cf. Definition 1 ) and they are applied to prove a sharpening of a classical result of Kleitman concerning families without k Pairwise Disjoint members.
-
families with no s Pairwise Disjoint sets
Journal of The London Mathematical Society-second Series, 2017Co-Authors: Peter Frankl, Andrey KupavskiiAbstract:For integers n >= s >= 2 let e (n, s) denote the maximum of vertical bar F vertical bar, where F is a family of subsets of an n- element set and F contains no s Pairwise Disjoint members. Half a century ago, solving a conjecture of Erd. os, Kleitman determined e(sm - 1, s) and e (sm, s) for all m, s >= 1. During the years very little progress in the general case was made. In the present paper we state a general conjecture concerning the value of e(sm - l, m) for 1 s(0) (l, m). For l = 2 we determine the value of e(sm - 2, m) for all s >= 5. Some related results shedding light on the problem from a more general context are also proved.
-
Families with no $s$ Pairwise Disjoint sets
Journal of the London Mathematical Society, 2017Co-Authors: Peter Frankl, Andrey KupavskiiAbstract:For integers $n\ge s\ge 2$ let $e(n,s)$ denote the maximum of $|\mathcal F|,$ where $\mathcal F$ is a family of subsets of an $n$-element set and $\mathcal F$ contains no $s$ Pairwise Disjoint members. Half a century ago, solving a conjecture of Erd\H os, Kleitman determined $e(sm-1,s)$ and $e(sm,s)$ for all $m,s\ge 1$. During the years very little progress in the general case was made. In the present paper we state a general conjecture concerning the value of $e(sm-l,m)$ for $1 s_0(l,m).$ For $l=2$ we determine the value of $e(sm-2,m)$ for all $s\ge 5.$ Some related results shedding light on the problem from a more general context are proved as well.
