Minimal spanning trees with a constraint on the number of leaves
From MaRDI portal
Publication:1291653
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)
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
