A note on graph balancing problems with restrictions

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

Research output: Contribution to journalArticlepeer-review

14 Scopus citations


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 languageEnglish (US)
Pages (from-to)24-29
Number of pages6
JournalInformation Processing Letters
Issue number1
StatePublished - Dec 1 2009

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications


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


Dive into the research topics of 'A note on graph balancing problems with restrictions'. Together they form a unique fingerprint.

Cite this