Orthogonal (g, f)-factorizations in networks

Peter Che Bor Lam; Guizhen Liu; Guojun Li; Wai Chee SHIU

doi:10.1002/1097-0037(200007)35:4<274::AID-NET6>3.0.CO;2-6

Orthogonal (g, f)-factorizations in networks

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

^*Corresponding author for this work

Department of Mathematics

Research output: Contribution to journal › Article › peer-review

28 Citations (Scopus)

2 Downloads (Pure)

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 H₁, H₂,⋯, H_k be subgraphs of G such that \E(H_i)\ = m, 1 ≤ i ≤ k, and V(H_i) ∩ V(W_j) = ø 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 H_i for i = 1, 2, ⋯, k and shown that there are polynomial-time algorithms to find the desired (g, f)-factorizations.

Original language	English
Pages (from-to)	274-278
Number of pages	5
Journal	Networks
Volume	35
Issue number	4
DOIs	https://doi.org/10.1002/1097-0037(200007)35:4<274::AID-NET6>3.0.CO;2-6
Publication status	Published - 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

Access to Document

10.1002/1097-0037(200007)35:4<274::AID-NET6>3.0.CO;2-6

Full Text

Cite this

@article{2f36fd8af93240d8aa3cfe7c74d4c1fb,

title = "Orthogonal (g, f)-factorizations in networks",

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) = {\o} 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.",

keywords = "network, graph, (g, f)-factorization, orthogonal factorization",

author = "Lam, {Peter Che Bor} and Guizhen Liu and Guojun Li and SHIU, {Wai Chee}",

year = "2000",

month = jul,

doi = "10.1002/1097-0037(200007)35:4<274::AID-NET6>3.0.CO;2-6",

language = "English",

volume = "35",

pages = "274--278",

journal = "Networks",

issn = "0028-3045",

publisher = "Wiley-Liss Inc.",

number = "4",

}

TY - JOUR

T1 - Orthogonal (g, f)-factorizations in networks

AU - Lam, Peter Che Bor

AU - Liu, Guizhen

AU - Li, Guojun

AU - SHIU, Wai Chee

PY - 2000/7

Y1 - 2000/7

N2 - 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.

AB - 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.

KW - network

KW - graph

KW - (g

KW - f)-factorization

KW - orthogonal factorization

UR - http://www.scopus.com/inward/record.url?scp=0034216160&partnerID=8YFLogxK

U2 - 10.1002/1097-0037(200007)35:4<274::AID-NET6>3.0.CO;2-6

DO - 10.1002/1097-0037(200007)35:4<274::AID-NET6>3.0.CO;2-6

M3 - Article

AN - SCOPUS:0034216160

SN - 0028-3045

VL - 35

SP - 274

EP - 278

JO - Networks

JF - Networks

IS - 4

ER -

Orthogonal (g, f)-factorizations in networks

Abstract

Scopus Subject Areas

User-Defined Keywords

Access to Document

Other files and links

Fingerprint

Cite this