Smaller Extended Formulations for the Spanning Tree Polytope of Bounded-Genus Graphs
Smaller Extended Formulations for the Spanning Tree Polytope of Bounded-Genus Graphs
复制标题
有界属图的生成树多形体的更小扩展公式
DOI：
10.1007/s00454-016-9852-9
复制
发表时间：
2016
影响因子：
0.8
通讯作者：
Kanstantsin Pashkovich
中科院分区：
文献类型：
--
作者：
Samuel Fiorini;T. Huynh;G. Joret;Kanstantsin Pashkovich
We give an O(g1/2n3/2+g3/2n1/2)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(g^{1/2} n^{3/2} + g^{3/2} n^{1/2})$$\end{document}-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)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n^2 + g n)$$\end{document}-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).
We give an O(g1/2n3/2+g3/2n1/2)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(g^{1/2} n^{3/2} + g^{3/2} n^{1/2})$$\end{document}-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)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n^2 + g n)$$\end{document}-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).
DOI：
10.1007/978-3-662-53536-3
发表时间：
2016
期刊：
--
影响因子：
--
作者：
P. Heggernes
通讯作者：
P. Heggernes
计数拟阵的子图多胞形和独立多胞形
DOI：
10.1016/j.orl.2015.06.011
发表时间：
2015
期刊：
ArXiv
影响因子：
--
作者：
Michele Conforti;Volker Kaibel;Matthias Walter;Stefan Weltge
通讯作者：
Stefan Weltge