Absorbant of generalized de Bruijn digraphs

Erfang Shan, Edwin Tai Chiu Cheng, Liying Kang

Research output: Journal article publicationJournal articleAcademic researchpeer-review

16 Citations (Scopus)

Abstract

The generalized de Bruijn digraph GB(n, d) has good properties as an interconnection network topology. The resource location problem in an interconnection network is one of the facility location problems. Finding absorbants of a digraph corresponds to solving a kind of resource location problem. In this paper, we establish bounds on the absorbant number for GB(n, d), and we give some sufficient conditions for the absorbant number of GB(n, d) to achieve the bounds. When d divides n, the extremal digraphs achieving the upper bound are characterized by determining their absorbants.
Original languageEnglish
Pages (from-to)6-11
Number of pages6
JournalInformation Processing Letters
Volume105
Issue number1
DOIs
Publication statusPublished - 31 Dec 2007

Keywords

  • Absorbant
  • Generalized de Bruijn digraph
  • Interconnection networks

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Cite this