TY - JOUR
T1 - A note on graph balancing problems with restrictions
AU - Lee, Kangbok
AU - Leung, Joseph Y.T.
AU - Pinedo, Michael L.
N1 - Funding Information:
E-mail addresses: [email protected] (K. Lee), [email protected] (J.Y.-T. Leung), [email protected] (M.L. Pinedo). 1 Work supported by the Korea Research Foundation Grant KRF-2007-357-D00270. 2 Work supported in part by the NSF Grant DMI-0556010. 3 Work supported in part by the NSF Grant DMI-0555999.
PY - 2009/12/1
Y1 - 2009/12/1
N2 - We consider the graph balancing problem of providing orientations to edges in an undirected multi-graph to minimize the maximum load. We first obtain an FPTAS when the multi-graph is restricted to a tree. We also obtain some additional results for other restricted cases by showing equivalencies with related combinatorial problems.
AB - We consider the graph balancing problem of providing orientations to edges in an undirected multi-graph to minimize the maximum load. We first obtain an FPTAS when the multi-graph is restricted to a tree. We also obtain some additional results for other restricted cases by showing equivalencies with related combinatorial problems.
KW - Approximation algorithm
KW - Combinatorial problems
KW - Computational complexity
KW - Eligibility constraints
KW - Fully polynomial time approximation scheme (FPTAS)
KW - Graph balancing
KW - Parallel machines scheduling
UR - http://www.scopus.com/inward/record.url?scp=70449526444&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=70449526444&partnerID=8YFLogxK
U2 - 10.1016/j.ipl.2009.09.015
DO - 10.1016/j.ipl.2009.09.015
M3 - Article
AN - SCOPUS:70449526444
SN - 0020-0190
VL - 110
SP - 24
EP - 29
JO - Information Processing Letters
JF - Information Processing Letters
IS - 1
ER -