Grid spanners | Zendy

Liestman Arthur L. | Zendy; Shermer Thomas C. | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Premium

Grid spanners

Author(s) -

Liestman Arthur L.,

Shermer Thomas C.

Publication year - 1993

Publication title -

networks

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.977

H-Index - 64

eISSN - 1097-0037

pISSN - 0028-3045

DOI - 10.1002/net.3230230206

Subject(s) - subnetwork , degree (music) , spanner , grid , constant (computer programming) , computer science , path (computing) , combinatorics , mathematics , distributed computing , computer network , physics , geometry , acoustics , programming language

A t ‐spanner of a network is a subnetwork in which every two nodes that were connected by an edge in the original network are connected by a path of at most t edges in the subnetwork. We present t ‐spanners with small maximum or average degree for multidimensional grids. We show how to construct small maximum degree 3‐spanners for d ‐dimensional grids for d © 2 and constant average degree 3‐spanners for d ‐dimensional grids. We also present t ‐spanners of minimum average degree for 2‐dimensional grids. © 1993 by John Wiley & Sons, Inc.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research