On finding spanning trees with few leaves
From MaRDI portal
Publication:2380066
DOI10.1016/j.ipl.2007.08.030zbMath1184.68647OpenAlexW1986398633MaRDI QIDQ2380066
Publication date: 24 March 2010
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2007.08.030
Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)
Related Items
Cutting-plane-based algorithms for two branch vertices related spanning tree problems ⋮ A 2k-vertex Kernel for Maximum Internal Spanning Tree ⋮ Solving the maximum internal spanning tree problem on interval graphs in polynomial time ⋮ Exact and heuristic solutions for the minimum number of branch vertices spanning tree problem ⋮ Scatter search for the minimum leaf spanning tree problem ⋮ Better Approximation Algorithms for the Maximum Internal Spanning Tree Problem ⋮ A simple linear time algorithm to solve the MIST problem on interval graphs ⋮ A \(\frac{4}{3}\)-approximation algorithm for the maximum internal spanning tree problem ⋮ Unrooted non-binary tree-based phylogenetic networks ⋮ On minimum leaf spanning trees and a criticality notion ⋮ Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree} ⋮ Decomposition methods based on articulation vertices for degree-dependent spanning tree problems ⋮ How far is my network from being edge-based? Proximity measures for edge-basedness of unrooted phylogenetic networks ⋮ An FPT algorithm for node-disjoint subtrees problems parameterized by treewidth ⋮ On spanning cycles, paths and trees ⋮ Spanning trees: A survey ⋮ A Polynomial Time Algorithm for Finding a Spanning Tree with Maximum Number of Internal Vertices on Interval Graphs ⋮ Better approximation algorithms for maximum weight internal spanning trees in cubic graphs and claw-free graphs ⋮ An approximation algorithm for maximum internal spanning tree ⋮ Depth first search in claw-free graphs ⋮ Relations, models and a memetic approach for three degree-dependent spanning tree problems ⋮ Unnamed Item ⋮ Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree ⋮ Better approximation algorithms for maximum weight internal spanning trees in cubic graphs and claw-free graphs ⋮ Approximation algorithms for the maximum weight internal spanning tree problem ⋮ Approximating the maximum internal spanning tree problem ⋮ On the minimum leaf number of cubic graphs ⋮ Algorithms for maximum internal spanning tree problem for some graph classes ⋮ Spanning k-ended trees of 3-regular connected graphs ⋮ Approximating spanning trees with few branches ⋮ Better approximation algorithms for the maximum internal spanning tree problem
Cites Work
