Minimum transversals of maximum matchings as approximate solutions to the bisection problem

DOI10.1007/BF02953326zbMath0858.05086MaRDI QIDQ1913329

Hans-Jürgen Bandelt, Thomas Andreae

Publication date: 1995

Published in: Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg (Search for Journal in Brave)

zbMATH Keywords

matchingtransversalsbisection problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (1)

On the traveling salesman problem restricted to inputs satisfying a relaxed triangle inequality

Cites Work

• Approximation algorithms for multi-dimensional assignment problems with decomposable costs
• A class of bounded approximation algorithms for graph partitioning
• Performance Guarantees for Approximation Algorithms Depending on Parametrized Triangle Inequalities
• Unnamed Item
• Unnamed Item

This page was built for publication: Minimum transversals of maximum matchings as approximate solutions to the bisection problem