×

zbMATH — the first resource for mathematics

Arborescence polytopes for series-parallel graphs. (English) Zbl 0802.05040
A graph is called series-parallel if it does not contain any subgraph homeomorphic to the complete graph on 4 vertices. For a directed graph whose underlying graph is series-parallel, an \(r\)-arborescence is defined as a tree directed away from the root vertex \(r\). Given a set of terminals, a Steiner arborescence is an \(r\)-arborescence spanning this set. Associated with these arborescences the author defines the convex hulls of incidence vectors and characterizes these polytopes completely by linear inequalities.

MSC:
05C20 Directed graphs (digraphs), tournaments
05C05 Trees
05C99 Graph theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Arnborg, S.; Lagergren, J.; Seese, D., Problems easy for tree-decomposable graphs, Research report, (1989)
[2] Arnborg, S.; Proskurowski, A., Linear time algorithms for NP-hard problems restricted to partial k-trees, Discrete appl. math., 23, 11-24, (1989) · Zbl 0666.68067
[3] Boulala, M.; Uhry, J.-P., Polytope des indépendants d’un graphe série-parallèle, Discrete math., 27, 225-243, (1979) · Zbl 0449.05065
[4] S. Chopra, The graph partitioning polytope on series-parallel and 4-wheel free graphs, SIAM J. Discrete Math., to appear. · Zbl 0797.05073
[5] Chopra, S., The equivalent subgraph and directed cut polyhedra on series-parallel graphs, SIAM J. discrete math., 5, 475-490, (1992) · Zbl 0774.05056
[6] Cornuéjols, G.; Fonlupt, J.; Naddef, D., The traveling salesman problem on a graph and some related integer polyhedra, Math. programming, 33, 1-27, (1985) · Zbl 0562.90095
[7] Coullard, C.R.; Rais, A.; Rardin, R.L.; Wagner, D.K., The 2-connected-spanning-subgraph polytope for series-parallel graphs, ()
[8] Duffin, R.J., Topology of series-parallel networks, J. math. anal. appl., 10, 303-318, (1965) · Zbl 0128.37002
[9] M.X. Goemans, The Steiner tree polytope and related polyhedra, Math. Programming, to appear. · Zbl 0808.90124
[10] Goemans, M.X., Polyhedral description of trees and arborescences, Proceedings of the 2nd integer programming and combinatorial optimization conference, 1-14, (1992), Pittsburgh, PA
[11] Goemans, M.X.; Myung, Y.-S., A catalog of Steiner tree formulations, Networks, 23, 19-28, (1993) · Zbl 0794.90074
[12] Liu, W., Extended formulations and polyhedral description, ()
[13] Mahjoub, A.R., On the stable set polytope of a series-parallel graph, Math. programming, 40, 53-57, (1988) · Zbl 0652.05029
[14] A.R. Mahjoub, Two edge connected spanning subgraphs and polyhedra, Math. Programming, to appear. · Zbl 0820.90117
[15] Nemhauser, G.; Wolsey, L.A., Integer and combinatorial optimization, (1988), Wiley New York · Zbl 0652.90067
[16] Prodon, A.; Liebling, T.M.; Gröflin, H., Steiner’s problem on 2-trees, ()
[17] Schaffers, M., A polynomial algorithm for the single source network flow design problem on series-parallel graphs, ()
[18] Schaffers, M., Network flow design III. polyhedral characterization of the single source fixed costs problem on series-parallel graphs, ()
[19] Segev, A., The node-weighted Steiner tree problem, Networks, 17, 1-18, (1987) · Zbl 0645.90092
[20] Takamizawa, K.; Nishizeki, T.; Saito, N., Linear-time computability of combinatorial problems on series-parallel graphs, J. ACM, 29, 623-641, (1982) · Zbl 0485.68055
[21] Wagner, D.K., Forbidden subgraphs and graph decomposition, Networks, 17, 105-110, (1987) · Zbl 0641.05047
[22] Wald, J.A.; Colbourn, C.J., Steiner trees, partial 2-trees, and minimum IFI networks, Networks, 13, 159-167, (1983) · Zbl 0529.68036
[23] Winter, P., Generalized Steiner problem in series-parallel networks, J. algorithms, 7, 549-566, (1986) · Zbl 0623.94023
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.