Approximation of the degree-constrained minimum spanning hierarchies

DOI10.1007/978-3-319-09620-9_9MaRDI QIDQ5496151zbMATH OpenOpenAlexFDO

Authors Miklos Molnar, Sylvain Durand, Massinissa Merabet

Publication date 7 August 2014

Published in Structural Information and Communication Complexity (Search for Journal in Brave)

Full work available at URL https://hal-lirmm.ccsd.cnrs.fr/lirmm-01056259/file/s_molnar_19_01056259_app%20%281%29.pdf

zbMATH Keywords

graph theorynetworksapproximationdegree-constrained spanning problemspanning hierarchy

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• ILP formulation of the degree-constrained minimum spanning hierarchy problem
• scientific article; zbMATH DE number 742978
• scientific article; zbMATH DE number 1163716
• A matter of degree: improved approximation algorithms for degree-bounded minimum spanning trees
• scientific article; zbMATH DE number 1054929

Cited in

(7)

• \(k\)-trails: recognition, complexity, and approximations
• ILP formulation of the degree-constrained minimum spanning hierarchy problem
• \(k\)-trails: recognition, complexity, and approximations
• scientific article; zbMATH DE number 6696497 (Why is no real title available?)
• Solving the degree-concentrated fault-tolerant spanning subgraph problem by DC programming
• DEGREE-CONSTRAINED MINIMUM SPANNING TREE PROBLEM IN STOCHASTIC GRAPH
• Layered graph models and exact algorithms for the generalized hop-constrained minimum spanning tree problem

This page was built for publication: Approximation of the degree-constrained minimum spanning hierarchies

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