The Experts below are selected from a list of 855 Experts worldwide ranked by ideXlab platform

Burkhard Monien - One of the best experts on this subject based on the ideXlab platform.

Nicholas C. Wormald - One of the best experts on this subject based on the ideXlab platform.

  • Minimum Power Dominating Sets of Random Cubic Graphs
    Journal of Graph Theory, 2016
    Co-Authors: Liying Kang, Nicholas C. Wormald
    Abstract:

    We present two heuristics for finding a small power dominating set of cubic graphs. We analyze the performance of these heuristics on random cubic graphs using differential equations. In this way, we prove that the proportion of vertices in a minimum power dominating set of a random cubic graph is asymptotically almost surely at most 0.067801. We also provide a corresponding lower bound of using known results on Bisection Width.

  • Bounds on the Bisection Width for random d -regular graphs
    Theoretical Computer Science, 2007
    Co-Authors: Josep Díaz, Maria Serna, Nicholas C. Wormald
    Abstract:

    In this paper we provide an explicit way to compute asymptotically almost sure upper bounds on the Bisection Width of random d-regular graphs, for any value of d. The upper bounds are obtained from the analysis of the performance of a randomized greedy algorithm to find Bisections of d-regular graphs. We provide bounds for 5≤d≤12. We also give empirical values of the size of the Bisection found by the algorithm for some small values of d and compare them with numerical approximations of our theoretical bounds. Our analysis also gives asymptotic lower bounds for the size of the maximum Bisection.

  • Computation of the Bisection Width for random d-regular graphs
    Lecture Notes in Computer Science, 2004
    Co-Authors: Josep Díaz, Maria Serna, Nicholas C. Wormald
    Abstract:

    In this paper we provide an explicit way to compute asymptotically almost sure upper bounds on the Bisection Width of random d-regular graphs, for any value of d. We provide the bounds for 5 < d < 12. The upper bounds are obtained from the analysis of the performance of a randomized greedy algorithm to find Bisections of d-regular graphs. We also give empirical values of the size of Bisection found by the algorithm for some small values of d and compare it with numerical approximations of our theoretical bounds. Our analysis also gives asymptotic lower bounds for the size of the maximum Bisection.

  • LATIN - Computation of the Bisection Width for Random d-Regular Graphs
    LATIN 2004: Theoretical Informatics, 2004
    Co-Authors: Josep Díaz, Maria Serna, Nicholas C. Wormald
    Abstract:

    In this paper we provide an explicit way to compute asymptotically almost sure upper bounds on the Bisection Width of random d-regular graphs, for any value of d. We provide the bounds for 5 ≤ d ≤ 12. The upper bounds are obtained from the analysis of the performance of a randomized greedy algorithm to find Bisections of d-regular graphs. We also give empirical values of the size of Bisection found by the algorithm for some small values of d and compare it with numerical approximations of our theoretical bounds. Our analysis also gives asymptotic lower bounds for the size of the maximum Bisection.

  • Bounds on the max and min Bisection of random cubic and random 4-regular graphs
    Theoretical Computer Science, 2003
    Co-Authors: Josep Díaz, Maria Serna, Nicholas C. Wormald
    Abstract:

    In this paper, we present a randomized algorithm to compute the Bisection Width of cubic and 4-regular graphs. The analysis of the proposed algorithms on random graphs provides asymptotic upper bounds for the Bisection Width of random cubic and random 4-regular graphs with n vertices, giving upper bounds of 0.174039n for random cubic, and of 0.333333n for random 4-regular. We also obtain asymptotic lower bounds for the size of the maximum Bisection, for random cubic and random 4-regular graphs with n vertices, of 1.32697n and 1.66667n, respectively. The randomized algorithms are derived from initial greedy algorithm and their analysis is based on the differential equation method.

Robert Preis - One of the best experts on this subject based on the ideXlab platform.

Josep Díaz - One of the best experts on this subject based on the ideXlab platform.

  • Bounds on the Bisection Width for random d -regular graphs
    Theoretical Computer Science, 2007
    Co-Authors: Josep Díaz, Maria Serna, Nicholas C. Wormald
    Abstract:

    In this paper we provide an explicit way to compute asymptotically almost sure upper bounds on the Bisection Width of random d-regular graphs, for any value of d. The upper bounds are obtained from the analysis of the performance of a randomized greedy algorithm to find Bisections of d-regular graphs. We provide bounds for 5≤d≤12. We also give empirical values of the size of the Bisection found by the algorithm for some small values of d and compare them with numerical approximations of our theoretical bounds. Our analysis also gives asymptotic lower bounds for the size of the maximum Bisection.

  • Computation of the Bisection Width for random d-regular graphs
    Lecture Notes in Computer Science, 2004
    Co-Authors: Josep Díaz, Maria Serna, Nicholas C. Wormald
    Abstract:

    In this paper we provide an explicit way to compute asymptotically almost sure upper bounds on the Bisection Width of random d-regular graphs, for any value of d. We provide the bounds for 5 < d < 12. The upper bounds are obtained from the analysis of the performance of a randomized greedy algorithm to find Bisections of d-regular graphs. We also give empirical values of the size of Bisection found by the algorithm for some small values of d and compare it with numerical approximations of our theoretical bounds. Our analysis also gives asymptotic lower bounds for the size of the maximum Bisection.

  • LATIN - Computation of the Bisection Width for Random d-Regular Graphs
    LATIN 2004: Theoretical Informatics, 2004
    Co-Authors: Josep Díaz, Maria Serna, Nicholas C. Wormald
    Abstract:

    In this paper we provide an explicit way to compute asymptotically almost sure upper bounds on the Bisection Width of random d-regular graphs, for any value of d. We provide the bounds for 5 ≤ d ≤ 12. The upper bounds are obtained from the analysis of the performance of a randomized greedy algorithm to find Bisections of d-regular graphs. We also give empirical values of the size of Bisection found by the algorithm for some small values of d and compare it with numerical approximations of our theoretical bounds. Our analysis also gives asymptotic lower bounds for the size of the maximum Bisection.

  • Bounds on the max and min Bisection of random cubic and random 4-regular graphs
    Theoretical Computer Science, 2003
    Co-Authors: Josep Díaz, Maria Serna, Nicholas C. Wormald
    Abstract:

    In this paper, we present a randomized algorithm to compute the Bisection Width of cubic and 4-regular graphs. The analysis of the proposed algorithms on random graphs provides asymptotic upper bounds for the Bisection Width of random cubic and random 4-regular graphs with n vertices, giving upper bounds of 0.174039n for random cubic, and of 0.333333n for random 4-regular. We also obtain asymptotic lower bounds for the size of the maximum Bisection, for random cubic and random 4-regular graphs with n vertices, of 1.32697n and 1.66667n, respectively. The randomized algorithms are derived from initial greedy algorithm and their analysis is based on the differential equation method.

  • RANDOM - Bisection of Random Cubic Graphs
    Randomization and Approximation Techniques in Computer Science, 2002
    Co-Authors: Josep Díaz, Maria Serna, Nicholas C. Wormald
    Abstract:

    We present two randomized algorithms to bound the Bisection Width of random n-vertex cubic graphs. We obtain an asymptotic upper bound for the Bisection Width of 0.174039n and a corresponding lower bound of 1.325961n. The analysis is based on the differential equation method.

Antonio Fernández Anta - One of the best experts on this subject based on the ideXlab platform.

  • Bisection (Band)Width of Product Networks with Application to Data Centers
    IEEE Transactions on Parallel and Distributed Systems, 2014
    Co-Authors: Jordi Arjona Aroca, Antonio Fernández Anta
    Abstract:

    The Bisection Width of interconnection networks has always been important in parallel computing, since it bounds the speed at which information can be moved from one side of a network to another, i.e., the Bisection bandWidth. Finding its exact value has proven to be challenging for some network families. For instance, the problem of finding the exact Bisection Width of the multidimensional torus was posed by Leighton [1, Problem 1.281] and has remained open for almost 20 years. We provide two general results that allow us to obtain upper and lower bounds on the Bisection Width of any product graph as a function of some properties of its factor graphs. The power of these results is shown by deriving the exact value of the Bisection Width of the torus, as well as of several d-dimensional classical parallel topologies that can be obtained by the application of the Cartesian product of graphs. We also apply these results to data centers, by obtaining bounds for the Bisection bandWidth of the d-dimensional BCube network, a recently proposed topology for data centers.

  • Bisection band Width of product networks with application to data centers
    Theory and Applications of Models of Computation, 2012
    Co-Authors: Jordi Arjona Aroca, Antonio Fernández Anta
    Abstract:

    The Bisection Width of interconnection networks has always been important in parallel computing, since it bounds the amount of information that can be moved from one side of a network to another, i.e., the Bisection bandWidth. The problem of finding the exact Bisection Width of the multidimensional torus was posed by Leighton and has remained open for 20 years. In this paper we provide the exact value of the Bisection Width of the torus, as well as of several d -dimensional classical parallel topologies that can be obtained by the application of the Cartesian product of graphs. To do so, we first provide two general results that allow to obtain upper and lower bounds on the Bisection Width of a product graph as a function of some properties of its factor graphs. We also apply these results to obtain bounds for the Bisection bandWidth of a d -dimensional BCube network, a recently proposed topology for data centers.

  • Bisection (Band)Width of Product Networks with Application to Data Centers
    arXiv: Networking and Internet Architecture, 2012
    Co-Authors: Jordi Arjona Aroca, Antonio Fernández Anta
    Abstract:

    The Bisection Width of interconnection networks has always been important in parallel computing, since it bounds the amount of information that can be moved from one side of a network to another, i.e., the Bisection bandWidth. Finding its exact value has proven to be challenging for some network families. For instance, the problem of finding the exact Bisection Width of the multidimensional torus was posed by Leighton and has remained open for almost 20 years. In this paper we provide the exact value of the Bisection Width of the torus, as well as of several d-dimensional classical parallel topologies that can be obtained by the application of the Cartesian product of graphs. To do so, we first provide two general results that allow to obtain upper and lower bounds on the Bisection Width of a product graph as a function of some properties of its factor graphs. We also apply these results to obtain bounds for the Bisection bandWidth of a d-dimensional BCube network, a recently proposed topology for data centers.

  • TAMC - Bisection (band)Width of product networks with application to data centers
    Lecture Notes in Computer Science, 2012
    Co-Authors: Jordi Arjona Aroca, Antonio Fernández Anta
    Abstract:

    The Bisection Width of interconnection networks has always been important in parallel computing, since it bounds the amount of information that can be moved from one side of a network to another, i.e., the Bisection bandWidth. The problem of finding the exact Bisection Width of the multidimensional torus was posed by Leighton and has remained open for 20 years. In this paper we provide the exact value of the Bisection Width of the torus, as well as of several d -dimensional classical parallel topologies that can be obtained by the application of the Cartesian product of graphs. To do so, we first provide two general results that allow to obtain upper and lower bounds on the Bisection Width of a product graph as a function of some properties of its factor graphs. We also apply these results to obtain bounds for the Bisection bandWidth of a d -dimensional BCube network, a recently proposed topology for data centers.

  • Bisection Width of Multidimensional ProductGraphs
    2011
    Co-Authors: Jordi Arjona Aroca, Antonio Fernández Anta
    Abstract:

    In this paper we will provide two general results that allow to obtain upper and lower bounds on the Bisection Width of a product graph as a function of some properties of its factor graphs. The most interesting contribution of this paper is the exact value of the Bisection Width of a d-dimensional torus, as this problem has been open for almost 20 years [2]. Our work is partially based on the work by Azizo�glu and E�gecio�glu. In [1] they study the relation between the isoperimetric number and the Bisection Width of diff�erent product networks and obtained and exact value for the Bisection Width of the d-dimensional array studying it as a product of paths. Similarly, we have been able to provide a lower and an upper bound for the Bisection Width of product graphs whose factor graphs have the same maximal congestion with multiplicity r, for the former case, or the same central cut, for the latter one. The general results provided are used to obtain exact bounds on the Bisection Width of several product graphs. The factor graphs used are paths, rings, complete binary trees (CBTs), and extended trees (which are CBTs with the leaves connected as a path). Then, we show that the Cartesian product of rings (i.e., the torus) of sizes k1 � : : : � kd has Bisection Width 2 Pei =1 Ci, where Ci = Qdj =i+1 kj for i 2 [1; e], and e being the lowest dimension with an even number of vertices. (If there is no such dimension, e = d.). Additionally, we show that the Cartesian product of a mixture of XTs and rings has the same Bisection Width. (When all factor graphs are XTs, e = d.) Finally, we show that the Cartesian product of a mixture of CBTs and paths has Bisection Width Pei =1 Ci. (When all factor graphs are CBTs, e = d.)