Spanning Trees with Many Leaves
From MaRDI portal
Publication:3360890
DOI10.1137/0404010zbMath0734.05041WikidataQ106158567 ScholiaQ106158567MaRDI QIDQ3360890
Douglas B. West, Daniel J. Kleitman
Publication date: 1991
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0404010
05C05: Trees
05C35: Extremal problems in graph theory
68R10: Graph theory (including graph drawing) in computer science
Related Items
A 3/2-Approximation Algorithm for Finding Spanning Trees with Many Leaves in Cubic Graphs, Spanning Trees with Many Leaves in Regular Bipartite Graphs, A 5/3-Approximation for Finding Spanning Trees with Many Leaves in Cubic Graphs, Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms, Better Algorithms and Bounds for Directed Maximum Leaf Problems, Leafy spanning trees in hypercubes, A \(9k\) kernel for nonseparating independent set in planar graphs, Kernel bounds for path and cycle problems, Improved bounds for spanning trees with many leaves, Max-leaves spanning tree is APX-hard for cubic graphs, Some results on spanning trees, On graphs with few disjoint \(t\)-star minors, A new algorithm for finding trees with many leaves, Spanning trees: A survey, Connected domination number of a graph and its complement, The complexity ecology of parameters: An illustration using bounded max leaf number, FPT algorithms and kernels for the directed \(k\)-leaf problem, Spanning trees in graphs of minimum degree 4 or 5, On the \(r\)-domination number of a graph, An exact algorithm for the maximum leaf spanning tree problem., Algorithmic meta-theorems for restrictions of treewidth, Bounds of the number of leaves of spanning trees in graphs without triangles, Bounds of the number of leaves of spanning trees, Hardness and approximation results for black hole search in arbitrary networks, On spanning cycles, paths and trees, Minimum degree, leaf number and traceability, Kernel Bounds for Path and Cycle Problems, Tight Bounds and a Fast FPT Algorithm for Directed Max-Leaf Spanning Tree