A note on “A linear‐size zero‐one programming model for the minimum spanning tree problem in planar graphs”

DOI10.1002/net.21849zbMath1409.90050OpenAlexW2898261852MaRDI QIDQ4628047

Hamidreza Validi, Austin Buchanan

Publication date: 6 March 2019

Published in: Networks (Search for Journal in Brave)

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

zbMATH Keywords

integer programmingspanning treeplanar graphextension complexityextended formulationplanar dualspanning arborescence

Mathematics Subject Classification ID

Integer programming (90C10) Communication networks in operations research (90B18) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items (4)

Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond ⋮ Imposing Contiguity Constraints in Political Districting Models ⋮ Linear-size formulations for connected planar graph partitioning and political districting ⋮ Parsimonious formulations for low-diameter clusters

Cites Work

• Unnamed Item
• Unnamed Item
• Extended formulations for sparsity matroids
• Extended formulations for independence polytopes of regular matroids
• Average case polyhedral complexity of the maximum stable set problem
• Smaller extended formulations for the spanning tree polytope of bounded-genus graphs
• Extended formulations, nonnegative factorizations, and randomized communication protocols
• Subgraph polytopes and independence polytopes of count matroids
• Small extended formulations for cyclic polytopes
• A linear-size zero?one programming model for the minimum spanning tree problem in planar graphs

This page was built for publication: A note on “A linear‐size zero‐one programming model for the minimum spanning tree problem in planar graphs”