On Tree-Constrained Matchings and Generalizations

DOI10.1007/978-3-642-22006-7_9zbMath1332.68057OpenAlexW1765664592MaRDI QIDQ3012795

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

Publication date: 6 July 2011

Published in: Automata, Languages and Programming (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) 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) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

Efficient exponential-time algorithms for edit distance between unordered trees ⋮ On tree-constrained matchings and generalizations

Uses Software

• Ct3d

Cites Work

• Geometric algorithms and combinatorial optimization
• The hardness of approximate optima in lattices, codes, and systems of linear equations
• On tree-constrained matchings and generalizations
• Scheduling Split Intervals
• A unified approach to approximating resource allocation and scheduling
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• On the hardness of approximating spanners
• Unnamed Item