The maximum-leaf spanning tree problem: Formulations and facets

DOI10.1002/NET.20001MaRDI QIDQ4474303zbMATH OpenOpenAlexFDO

Authors Tetsuya Fujie

Publication date 4 August 2004

Published in Networks (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/net.20001

zbMATH Keywords

facetsinteger programmingspanning treesvalid inequalities

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Communication networks in operations research (90B18) Integer programming (90C10)

Recommendations

• An exact algorithm for the maximum leaf spanning tree problem.
• Reformulations and solution algorithms for the maximum leaf spanning tree problem
• Flow-based formulation for the maximum leaf spanning tree problem
• Spanning trees with a constraint on the number of leaves. A new formulation
• Spanning Trees with Many Leaves

Cites work

• Approximation algorithms for connected dominating sets
• Graph theory with applications
• scientific article; zbMATH DE number 193411 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)

Cited in

(24)

• An exact algorithm for the maximum leaf spanning tree problem.
• The maximum \(f\)-depth spanning tree problem
• Spanning trees with a constraint on the number of leaves. A new formulation
• Regenerator location problem: polyhedral study and effective branch-and-cut algorithms
• A branch-and-Benders-cut approach for the fault tolerant regenerator location problem
• On connected dominating sets of restricted diameter
• On maximum leaf trees and connections to connected maximum cut problems
• Complexity of the maximum leaf spanning tree problem on planar and regular graphs
• Benders decomposition, branch-and-cut, and hybrid algorithms for the minimum connected dominating set problem
• scientific article; zbMATH DE number 6611438 (Why is no real title available?)
• The regenerator location problem
• Finding totally independent spanning trees with linear integer programming
• Flow-based formulation for the maximum leaf spanning tree problem
• scientific article; zbMATH DE number 5777935 (Why is no real title available?)
• Complexity of spanning tree problems with leaf-dependent objectives
• A Fast Vertex Weighting-Based Local Search for Finding Minimum Connected Dominating Sets
• A 2-approximation algorithm for finding a spanning tree with maximum number of leaves
• The optimal design of low-latency virtual backbones
• Spanning Trees with Many Leaves in Regular Bipartite Graphs
• Kernelization for Maximum Leaf Spanning Tree with Positive Vertex Weights
• Branch‐and‐cut algorithms for the ‐arborescence star problem
• Solving Steiner trees: Recent advances, challenges, and perspectives
• Optimization of wireless sensor networks deployment with coverage and connectivity constraints
• Reformulations and solution algorithms for the maximum leaf spanning tree problem

Describes a project that uses

Uses Software

• cdd

This page was built for publication: The maximum-leaf spanning tree problem: Formulations and facets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4474303)