Complexity of the multiobjective minimum weight minimum stretch spanner problem

DOI10.1007/S00186-024-00850-7MaRDI QIDQ6616272zbMATH OpenFDO

Authors Fritz Bökler, Henning Jasper

Publication date 9 October 2024

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

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/S00186-024-00850-7

zbMATH Keywords

extreme pointsgraph spannersmultiobjective optimizationoutput-sensitive complexityparametric optimization

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Publication:4733693
• On spanning tree problems with multiple objectives
• scientific article; zbMATH DE number 3980505
• scientific article; zbMATH DE number 1107724
• The problem of the optimal biobjective spanning tree

Cites work

• A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
• Algorithms – ESA 2004
• An Optimal Synchronizer for the Hypercube
• Approximating Multiobjective Shortest Path in Practice
• Generating Sparse 2-Spanners
• Graph spanners
• scientific article; zbMATH DE number 3694968 (Why is no real title available?)
• scientific article; zbMATH DE number 6737879 (Why is no real title available?)
• Multicriteria Optimization
• NP-completeness of minimum spanner problems
• NP-hardness and fixed-parameter tractability of the minimum spanner problem
• On cardinality of the set of alternatives in discrete many-criterion problems
• On generating all maximal independent sets
• On spanning tree problems with multiple objectives
• On sparse spanners of weighted graphs
• Output-sensitive algorithms for enumerating the extreme nondominated points of multiobjective combinatorial optimization problems
• Spanners in graphs of bounded degree
• The complexity of theorem-proving procedures
• Tree Spanners

Cited in

(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)