TY - JOUR
T1 - Orthogonal (g, f)-factorizations in networks
AU - Lam, Peter Che Bor
AU - Liu, Guizhen
AU - Li, Guojun
AU - Shiu, Wai Chee
N1 - Copyright:
Copyright 2017 Elsevier B.V., All rights reserved.
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 - Journal article
AN - SCOPUS:0034216160
SN - 0028-3045
VL - 35
SP - 274
EP - 278
JO - Networks
JF - Networks
IS - 4
ER -