Orthogonal (g, f)-factorizations in networks

Peter Che Bor Lam*, Guizhen Liu, Guojun Li, Wai Chee SHIU

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

27 Citations (Scopus)

Abstract

Let G = (V, E) be a graph and let g and f be two integer-valued functions defined on V such that k ≤ g(x) ≤ f(x) for all x ∈ V. Let H1, H2,⋯, Hk be subgraphs of G such that \E(Hi)\ = m, 1 ≤ i ≤ k, and V(Hi) ∩ V(Wj) = ø when i ≠ j. In this paper, it is proved that every (mg + m - 1, mf - m + 1)-graph G has a (g, f)-factorization orthogonal to Hi for i = 1, 2, ⋯, k and shown that there are polynomial-time algorithms to find the desired (g, f)-factorizations.

Original languageEnglish
Pages (from-to)274-278
Number of pages5
JournalNetworks
Volume35
Issue number4
DOIs
Publication statusPublished - Jul 2000

Scopus Subject Areas

  • Software
  • Information Systems
  • Hardware and Architecture
  • Computer Networks and Communications

User-Defined Keywords

  • network
  • graph
  • (g
  • f)-factorization
  • orthogonal factorization

Fingerprint

Dive into the research topics of 'Orthogonal (g, f)-factorizations in networks'. Together they form a unique fingerprint.

Cite this