Complexity of the multiobjective minimum weight minimum stretch spanner problem

DOI10.1007/S00186-024-00850-7MaRDI QIDQ6616272

Fritz Bökler, Henning Jasper

Publication date: 9 October 2024

Published in: Mathematical Methods of Operations Research (Search for Journal in Brave)

zbMATH Keywords

parametric optimizationextreme pointsmultiobjective optimizationgraph spannersoutput-sensitive complexity

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• On generating all maximal independent sets
• On sparse spanners of weighted graphs
• NP-completeness of minimum spanner problems
• On spanning tree problems with multiple objectives
• NP-hardness and fixed-parameter tractability of the minimum spanner problem
• Output-Sensitive Algorithms for Enumerating the Extreme Nondominated Points of Multiobjective Combinatorial Optimization Problems
• Graph spanners
• On cardinality of the set of alternatives in discrete many-criterion problems
• Spanners in graphs of bounded degree
• Generating Sparse 2-Spanners
• An Optimal Synchronizer for the Hypercube
• Tree Spanners
• Approximating Multiobjective Shortest Path in Practice
• A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
• Multicriteria Optimization
• Improved smoothed analysis of multiobjective optimization
• Algorithms – ESA 2004
• The complexity of theorem-proving procedures

Related Items (1)

Special issue on exact and approximation methods for mixed-integer multi-objective optimization

This page was built for publication: Complexity of the multiobjective minimum weight minimum stretch spanner problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6616272)