A self-stabilizing 3-approximation for the maximum leaf spanning tree problem in arbitrary networks

DOI10.1007/S10878-011-9383-5MaRDI QIDQ2377384zbMATH OpenOpenAlexFDO

Authors Sayaka Kamei, Hirotsugu Kakugawa, Stéphane Devismes, Sébastien Tixeuil

Publication date 28 June 2013

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial 4.0 International

Full work available at URL https://doi.org/10.1007/s10878-011-9383-5

zbMATH Keywords

approximationfault-tolerancemaximum leaf spanning treeself-stabilization

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• A self-stabilizing 3-approximation for the maximum leaf spanning tree problem in arbitrary networks
• A maximum degree self-stabilizing spanning tree algorithm
• A self-stabilizing distributed algorithm to construct an arbitrary spanning tree of a connected graph
• scientific article; zbMATH DE number 1305098
• Approximating Maximum Leaf Spanning Trees in Almost Linear Time

Cites work

• A New Self-stabilizing Minimum Spanning Tree Construction with Loop-Free Property
• A short note on the approximability of the maximum leaves spanning tree problem
• A uniform self-stabilizing minimum diameter spanning tree algorithm
• Approximating Maximum Leaf Spanning Trees in Almost Linear Time
• Fast self-stabilizing Byzantine tolerant digital clock synchronization
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1305098 (Why is no real title available?)
• scientific article; zbMATH DE number 1332668 (Why is no real title available?)
• scientific article; zbMATH DE number 2061548 (Why is no real title available?)
• Self-stabilization
• Self-stabilizing clock synchronization in the presence of Byzantine faults
• Self-stabilizing minimum degree spanning tree within one from the optimal degree
• Self-stabilizing systems in spite of distributed control
• Stabilization of general loop-free routing
• Unifying self-stabilization and fault-tolerance
• Wait-free clock synchronization

Cited in

(6)

• A self-stabilizing distributed algorithm for spanning tree construction in wireless ad hoc networks.
• Connected domination in maximal outerplanar graphs
• Self-Stabilizing Domination Algorithms
• A self-stabilizing 3-approximation for the maximum leaf spanning tree problem in arbitrary networks
• A maximum degree self-stabilizing spanning tree algorithm
• A 2-approximation algorithm for finding a spanning tree with maximum number of leaves

This page was built for publication: A self-stabilizing 3-approximation for the maximum leaf spanning tree problem in arbitrary networks

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