Balanced paths in acyclic networks: Tractable cases and related approaches

DOI10.1002/net.20053zbMath1067.68012OpenAlexW4241786443MaRDI QIDQ4667719

Paola Cappanera, Maria Grazia Scutellà

Publication date: 21 April 2005

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.20053

zbMATH Keywords

balanced pathslayered networkscost differencepseudopolynomial approaches

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10)

Related Items (8)

Inequity averse optimization in operational research ⋮ The balanced traveling salesman problem ⋮ A branch-and-cut algorithm for the balanced traveling salesman problem ⋮ Balanced Optimization with Vector Costs ⋮ Robust balanced optimization ⋮ Exact algorithms for the equitable traveling salesman problem ⋮ Approximation algorithms for the load-balanced capacitated vehicle routing problem ⋮ The quadratic balanced optimization problem

Cites Work

• Unnamed Item
• Unnamed Item
• The complexity of finding two disjoint paths with min-max objective function
• 1-Approximation algorithm for bottleneck disjoint path matching
• Balanced optimization problems
• A multi-level bottleneck assignment approach to the bus drivers' rostering problem
• Most and least uniform spanning trees
• Some simplified NP-complete graph problems
• The balanced linear programming problem
• A strongly polynomial algorithm for the uniform balanced network flow problem
• Approximating disjoint-path problems using packing integer programs
• Disjoint paths in a network
• Finding Two Disjoint Paths Between Two Pairs of Vertices in a Graph
• Color-coding
• A Column Generation Approach for Large-Scale Aircrew Rostering Problems
• The complexity of finding maximum disjoint paths with length constraints
• A Multicommodity Flow Approach to the Crew Rostering Problem
• Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems

This page was built for publication: Balanced paths in acyclic networks: Tractable cases and related approaches