Minimal spanning trees with a constraint on the number of leaves

DOI10.1016/S0377-2217(96)00327-XzbMath0957.90010MaRDI QIDQ1291653

Lucinda Matos Fernandes, Luís Gouveia

Publication date: 22 March 2001

Published in: European Journal of Operational Research (Search for Journal in Brave)

zbMATH Keywords

integer linear programminglinear programming relaxationsspanning trees

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Deterministic network models in operations research (90B10)

Related Items (22)

Cutting-plane-based algorithms for two branch vertices related spanning tree problems ⋮ Bounds on the leaf number in graphs of girth 4 or 5 ⋮ Min-degree constrained minimum spanning tree problem: complexity, properties, and formulations ⋮ Connectivity, traceability and Hamiltonicity ⋮ The Generalized Regenerator Location Problem ⋮ Spanning trees with a constraint on the number of leaves. A new formulation ⋮ Finding Totally Independent Spanning Trees with Linear Integer Programming ⋮ Hamiltonicity, minimum degree and leaf number ⋮ Solving Steiner trees: Recent advances, challenges, and perspectives ⋮ Radius, leaf number, connected domination number and minimum degree ⋮ Leaf number and Hamiltonian \(C_4\)-free graphs ⋮ Decomposition methods based on articulation vertices for degree-dependent spanning tree problems ⋮ An exact algorithm for the maximum leaf spanning tree problem. ⋮ Graphs with forbidden subgraphs and leaf number ⋮ On spanning cycles, paths and trees ⋮ Spanning paths in graphs ⋮ Spanning paths and cycles in triangle-free graphs ⋮ On minimum degree, leaf number, traceability and Hamiltonicity in graphs ⋮ Relations, models and a memetic approach for three degree-dependent spanning tree problems ⋮ A personalized walking bus service requiring optimized route decisions: a real case ⋮ Reformulations and solution algorithms for the maximum leaf spanning tree problem ⋮ Minimum degree, leaf number and traceability

Cites Work

• Unnamed Item
• Unnamed Item
• A Lagrangean approach to the degree-constrained minimum spanning tree problem
• Multicommodity flow models for spanning trees with hop constraints
• A short note on the approximability of the maximum leaves spanning tree problem
• Topological design of centralized computer networks—formulations and algorithms
• An Efficient Algorithm for the Min-Sum Arborescence Problem on Complete Digraphs
• Validation of subgradient optimization
• A 2n Constraint Formulation for the Capacitated Minimal Spanning Tree Problem

This page was built for publication: Minimal spanning trees with a constraint on the number of leaves