Name
Abstract | ||
|---|---|---|
Let G be a simple finite connected undirected graph. A contraction φ of G is a mapping from G = G ( V , E ) to G ′ = G ′( V ′, E ′), where G ′ is also a simple connected undirected graph, such that if u , ν ∈ V are connected by an edge (adjacent) in G then either φ( u ) = φ(ν), or φ( u ) and φ(ν) are adjacent in G ′. In this paper we are interested in a family of contractions, called bounded contractions, in which ∀ν′ ∈ V ′, the degree of ν′ in G ′, Deg G ′ (ν′), satisfies Deg G ′ (ν′) ≤ |φ −1 (ν′)|, where φ −1 (ν′) denotes the set of vertices in G mapped to ν′ under φ. These types of contractions are useful in the assignment (mapping) of parallel programs to a network of interconnected processors, where the number of communication channels of each processor is small. The main results of this paper are that there exists a partitioning of full m -ary trees that yields a bounded contraction of degree m + 1, i.e., a mapping for which ∀ν′ ∈ V ′, |φ −1 (ν′)| ≤ m + 1, and that this degree is a lower bound, i.e., there is no mapping of a full m -ary tree such that ∀ν′ ∈ V ′, |φ −1 (ν′)| ≤ m |
Year | DOI | Venue |
|---|---|---|
1993 | 10.1006/jpdc.1993.1035 | J. Parallel Distrib. Comput. |
Keywords | Field | DocType |
bounded contraction,full tree | Graph theory,Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Bound graph,Upper and lower bounds,Mathematics,Bounded function,Distributed computing | Journal |
Volume | Issue | ISSN |
17 | 4 | Journal of Parallel and Distributed Computing |
Citations | PageRank | References |
3 | 0.51 | 0 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Amnon Barak | 1 | 590 | 119.00 |
| Ron Ben-Natan | 2 | 6 | 1.87 |