Finding a minimum spanning tree with a small non-terminal set

DOI10.1016/J.TCS.2025.115092MaRDI QIDQ7021844zbMATH OpenFDO

Authors Tesshu Hanaka, Yasuaki Kobayashi

Publication date 26 February 2025

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2025.115092

zbMATH Keywords

fixed-parameter algorithmskernelizationparameterized complexityspanning tree

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• A 4k^2 kernel for feedback vertex set
• A \(\frac{4}{3}\)-approximation algorithm for the maximum internal spanning tree problem
• A linear vertex kernel for maximum internal spanning tree
• A weighted matroid intersection algorithm
• Algorithms for maximum internal spanning tree problem for some graph classes
• An approximation algorithm for maximum internal spanning tree
• Another look at the degree constrained subgraph problem
• Counting Minimum Weight Spanning Trees
• Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree
• Easy problems for tree-decomposable graphs
• Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree}
• Exact exponential algorithms.
• Exploring the gap between treedepth and vertex cover through vertex integrity
• Fast Polynomial-Space Algorithms Using Möbius Inversion: Improving on Steiner Tree and Related Problems
• HAMILTONian circuits in chordal bipartite graphs
• Hitting forbidden minors: approximation and kernelization
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 5047784 (Why is no real title available?)
• Intractability of clique-width parameterizations
• Kernel bounds for path and cycle problems
• Kernelization Lower Bounds by Cross-Composition
• New limits to classical and quantum instance compression
• On the minimum diameter spanning tree problem
• On the terminal connection problem
• Parameterized algorithms
• Solving the maximum internal spanning tree problem on interval graphs in polynomial time
• Spanning tree with lower bound on the degrees
• Spanning Trees with Many Leaves
• Spanning trees with vertices having large degrees
• Sparsity. Graphs, structures, and algorithms
• Spotting trees with few leaves
• The complexity ecology of parameters: An illustration using bounded max leaf number
• The minimum spanning tree problem with non-terminal set
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• WALCOM: algorithms and computation. 18th international conference and workshops on algorithms and computation, WALCOM 2024, Kanazawa, Japan, March 18--20, 2024. Proceedings

This page was built for publication: Finding a minimum spanning tree with a small non-terminal set

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