A note on graph balancing problems with restrictions

Kangbok Lee; Joseph Y.T. Leung; Michael L. Pinedo

doi:10.1016/j.ipl.2009.09.015

A note on graph balancing problems with restrictions

Kangbok Lee
, Joseph Y.T. Leung
, Michael L. Pinedo

Computer Science

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

15 Scopus citations

Abstract

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.

Original language	English (US)
Pages (from-to)	24-29
Number of pages	6
Journal	Information Processing Letters
Volume	110
Issue number	1
DOIs	https://doi.org/10.1016/j.ipl.2009.09.015
State	Published - Dec 1 2009

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Keywords

Approximation algorithm
Combinatorial problems
Computational complexity
Eligibility constraints
Fully polynomial time approximation scheme (FPTAS)
Graph balancing
Parallel machines scheduling

Access to Document

10.1016/j.ipl.2009.09.015

Cite this

@article{c1b67f768f3e4651bc8a4798dad84da8,

title = "A note on graph balancing problems with restrictions",

abstract = "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.",

keywords = "Approximation algorithm, Combinatorial problems, Computational complexity, Eligibility constraints, Fully polynomial time approximation scheme (FPTAS), Graph balancing, Parallel machines scheduling",

author = "Kangbok Lee and Leung, \{Joseph Y.T.\} and Pinedo, \{Michael L.\}",

note = "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.",

year = "2009",

month = dec,

day = "1",

doi = "10.1016/j.ipl.2009.09.015",

language = "English (US)",

volume = "110",

pages = "24--29",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "1",

}

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 - https://www.scopus.com/pages/publications/70449526444

UR - https://www.scopus.com/pages/publications/70449526444#tab=citedBy

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 -

A note on graph balancing problems with restrictions

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this