Approximation algorithms for multi-parameter graph optimization problems

DOI10.1016/S0166-218X(01)00269-4zbMath1041.90059WikidataQ126717791 ScholiaQ126717791MaRDI QIDQ1602708

Ivan V. Basov, A. D. Vaĭnshteĭn

Publication date: 24 June 2002

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

approximation algorithmweakly NP-hard

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (1)

A fully polynomial bicriteria approximation scheme for the constrained spanning tree problem.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The shortest route problem with constraints
• Algorithms for finding paths with multiple constraints
• Approximation of Pareto Optima in Multiple-Objective, Shortest-Path Problems
• Maximizing Classes of Two-Parameter Objectives Over Matroids
• Approximation Schemes for the Restricted Shortest Path Problem
• Bicriteria Network Design Problems
• The constrained minimum spanning tree problem
• The network inhibition problem

This page was built for publication: Approximation algorithms for multi-parameter graph optimization problems