On tree-constrained matchings and generalizations

DOI10.1007/s00453-013-9785-0zbMath1307.05181OpenAlexW2121472099MaRDI QIDQ2258075

Stefan Canzar, Gunnar W. Klau, Julián Mestre, Khaled M. Elbassioni

Publication date: 2 March 2015

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://hal.inria.fr/hal-01248542/file/tree_matching.pdf

zbMATH Keywords

computational biologyapproximation algorithmsrooted treesinapproximability\(k\)-partite matchinglocal ratio technique

Mathematics Subject Classification ID

Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25)

Related Items

Approximating weighted neighborhood independent sets ⋮ On Tree-Constrained Matchings and Generalizations ⋮ Approximating weighted induced matchings ⋮ Isomorphic unordered labeled trees up to substitution ciphering

Uses Software

• Ct3d

Cites Work

• Unnamed Item
• Unnamed Item
• Geometric algorithms and combinatorial optimization
• The hardness of approximate optima in lattices, codes, and systems of linear equations
• On Tree-Constrained Matchings and Generalizations
• Iterative Methods in Combinatorial Optimization
• Elimination graphs
• Scheduling Split Intervals
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• On the hardness of approximating spanners