Name
Title | ||
|---|---|---|
Smaller Extended Formulations for the Spanning Tree Polytope of Bounded-genus Graphs. |
Abstract | ||
|---|---|---|
We give an $$O(g^{1/2} n^{3/2} + g^{3/2} n^{1/2})$$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(n^2 + g n)$$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). |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1007/s00454-016-9852-9 | Discrete & Computational Geometry |
Keywords | DocType | Volume |
Spanning tree polytope,Extended formulation,Genus | Journal | abs/1604.07976 |
Issue | ISSN | Citations |
3 | 0179-5376 | 0 |
PageRank | References | Authors |
0.34 | 3 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Samuel Fiorini | 1 | 402 | 42.93 |
| Tony Huynh | 2 | 11 | 9.36 |
| Gwenaël Joret | 3 | 196 | 28.64 |
| Kanstantsin Pashkovich | 4 | 97 | 15.24 |