✦ LIBER ✦

The minumum geodetic communication overlap graphs

✍ Scribed by J. Nieminen; M. Peltola

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 231 KB
Volume: 11
Category: Article
ISSN: 0893-9659
DOI: 10.1016/s0893-9659(98)00018-4

No coin nor oath required. For personal study only.

✦ Synopsis

We develop further the communication overlap index of Hong and Zuo in the case where the points of the graph communicate with each other through shortest paths (geodesics) of the graph. The structure of the graphs with minimum geodetic communication index is described, the concept of geodetic connectivity of a graph introduced, and a condition for testing the geodetic connectivity of a graph given.

📜 SIMILAR VOLUMES

The geodetic number of a graph

✍ Frank Harary; Emmanuel Loukakis; Constantine Tsouros 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 406 KB

The recognition of geodetically connecte

The recognition of geodetically connected graphs

✍ Jou-Ming Chang; Chin-Wen Ho 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 849 KB

Let G = ( y E) be a graph with vertex set V of size n and edge set E of size m. A vertex LJ E V is called a hinge vertex if the distance of any two vertices becomes longer after u is removed. A graph without hinge vertex is called a hinge-free graph. In general, a graph G is k-geodetically connected

On the geodetic number of a graph

✍ Gary Chartrand; Frank Harary; Ping Zhang 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 308 KB

The Geodetic Number of an Oriented Graph

✍ Gary Chartrand; Ping Zhang 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 149 KB

For two vertices u and v of an oriented graph D, the set I (u, v) consists of all vertices lying on a uv geodesic or vu geodesic in D. If S is a set of vertices of D, then I (S) is the union of all sets I (u, v) for vertices u and v in S. The geodetic number g(D) is the minimum cardinality among the

On the chromatic number of multiple inte

On the chromatic number of multiple interval graphs and overlap graphs

✍ A. Gyárfás 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 374 KB

Let x(G) and o(G) denote the chromatic number and clique number of a graph G. We prove that x can be bounded by a function of o for two well-known relatives of interval graphs. Multiple interval graphs (the intersection graphs of sets which can be written as the union of t closed intervals of a line

On the Utility of Communication–Computat

On the Utility of Communication–Computation Overlap in Data-Parallel Programs

✍ Michael J. Quinn; Philip J. Hatcher 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 260 KB

However, the speedup achieved through parallelism is often lower in modern systems. It is no surprise, then, that developers of compilers for data-parallel languages have hypothesized the importance of optimizations that overlap communications with computations in order to reduce execution times and