Finding spanning trees with perfect matchings

DOI10.1016/J.DAM.2025.04.001MaRDI QIDQ6982339zbMATH OpenFDO

Authors Kristóf Bérczi, Tamás Király, Yusuke Kobayashi, Yutaro Yamaguchi, Yu Yokoi

Publication date 19 May 2025

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.DAM.2025.04.001

zbMATH Keywords

algorithmNP-hardnessperfect matchingspanning tree

Mathematics Subject Classification ID

Trees (05C05) Signed and weighted graphs (05C22) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites work

• A note on two problems in connexion with graphs
• A theory of alternating paths and blossoms from the perspective of minimum length
• Algebraic algorithms for matching and matroid problems
• AN ALGORITHM FOR FINDING AN OPTIMAL "INDEPENDENT ASSIGNMENT"
• Approximating minimum bounded degree spanning trees to within one of optimal
• Approximating the Minimum-Degree Steiner Tree to within One of Optimal
• Bounded degree spanning trees (extended abstract)
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Complexity of paired domination in AT-free and planar graphs
• Computing a (1+)-approximate geometric minimum-diameter spanning tree
• Connections in combinatorial optimization
• Discrete Convex Analysis
• Enumeration of spanning trees containing perfect matchings in hexagonal chains with a unique kink
• Faster matrix multiplication via asymmetric hashing
• Graphs where each spanning tree has a perfect matching
• scientific article; zbMATH DE number 3694608 (Why is no real title available?)
• scientific article; zbMATH DE number 3404256 (Why is no real title available?)
• Labelling algorithms for paired-domination problems in block and interval graphs
• Matroid Intersection
• Matroid intersection algorithms
• Maximum matching and a polyhedron with 0,1-vertices
• Minimum restricted diameter spanning trees.
• On the anti-forcing number of benzenoids
• On the minimum diameter spanning tree problem
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Paired-domination in graphs
• Paths, Trees, and Flowers
• Planar Formulae and Their Uses
• Submodular functions and optimization.
• Two algorithms for weighted matroid intersection

Cited in

(1)

• Parameterized spanning tree congestion

This page was built for publication: Finding spanning trees with perfect matchings

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