On the complexity of the bilevel minimum spanning tree problem

DOI10.1002/net.22111arXiv2012.12770WikidataQ114235444 ScholiaQ114235444MaRDI QIDQ6064168

Christoph Buchheim, Felix Hommelsheim, Dorothee Henke

Publication date: 12 December 2023

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2012.12770

zbMATH Keywords

complexitycombinatorial optimizationapproximation algorithmsSteiner treebilevel optimizationspanning tree problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• A factor 2 approximation algorithm for the generalized Steiner network problem
• The Steiner tree problem on graphs: inapproximability results
• The computational complexity of bilevel assignment problems
• The Steiner problem with edge lengths 1 and 2
• Graph minors. XIII: The disjoint paths problem
• An overview of bilevel optimization
• An overview of Stackelberg pricing in networks
• New Branch-and-Bound Rules for Linear Bilevel Programming
• Annotated Bibliography on Bilevel Programming and Mathematical Programs with Equilibrium Constraints
• Bilevel Programming Problems
• On bilevel minimum and bottleneck spanning tree problems
• Shortest Two Disjoint Paths in Polynomial Time
• The steiner problem in graphs
• Bilevel programming and price setting problems
• Computational comparisons of different formulations for the Stackelberg minimum spanning tree game
• A survey on mixed-integer programming techniques in bilevel optimization

This page was built for publication: On the complexity of the bilevel minimum spanning tree problem