A note on graph balancing problems with restrictions

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

Research output: Contribution to journalArticlepeer-review

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

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

Cite this