A Note on Graph Balancing Problems with Restrictions
SCIE
SCOPUS
- Title
- A Note on Graph Balancing Problems with Restrictions
- Authors
- Lee, K; Leung, JYT; Pinedo, ML
- Date Issued
- 2009-12-01
- Publisher
- ELSEVIER SCIENCE BV
- 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. (C) 2009 Elsevier B.V. All rights reserved.
- URI
- https://oasis.postech.ac.kr/handle/2014.oak/36386
- DOI
- 10.1016/J.IPL.2009.09.015
- ISSN
- 0020-0190
- Article Type
- Article
- Citation
- INFORMATION PROCESSING LETTERS, vol. 110, no. 1, page. 24 - 29, 2009-12-01
- Files in This Item:
- There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.