We give an O(g1 / 2n3 / 2+ g3 / 2n1 / 2) -size extended formulation for the spanning tree polytope of an n-vertex graph embedded in a surface of genus g, improving on the known O(n2+ gn) -size extended formulations following from Wong (Proceedings of 1980 IEEE International Conference on Circuits and Computers, pp 149–152, 1980) and Martin (Oper Res Lett 10:119–128, 1991).
Smaller Extended Formulations for the Spanning Tree Polytope of Bounded-Genus Graphs / Fiorini, S.; Huynh, T.; Joret, G.; Pashkovich, K.. - In: DISCRETE & COMPUTATIONAL GEOMETRY. - ISSN 0179-5376. - 57:3(2017), pp. 757-761. [10.1007/s00454-016-9852-9]
Smaller Extended Formulations for the Spanning Tree Polytope of Bounded-Genus Graphs
Huynh T.;Joret G.;
2017
Abstract
We give an O(g1 / 2n3 / 2+ g3 / 2n1 / 2) -size extended formulation for the spanning tree polytope of an n-vertex graph embedded in a surface of genus g, improving on the known O(n2+ gn) -size extended formulations following from Wong (Proceedings of 1980 IEEE International Conference on Circuits and Computers, pp 149–152, 1980) and Martin (Oper Res Lett 10:119–128, 1991).File allegati a questo prodotto
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
