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

DOI10.1007/BF02953326MaRDI QIDQ1913329zbMATH OpenFDO

Authors 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)

Full work available at URL https://doi.org/10.1007/BF02953326

zbMATH Keywords

bisection problemmatchingtransversals

Mathematics Subject Classification ID

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

Recommendations

• A 2-approximation for the maximum satisfying bisection problem
• scientific article; zbMATH DE number 1929926
• Tight inapproximability of minimum maximal matching on bipartite graphs and related problems
• Approximating the minimum bisection size (extended abstract)
• scientific article; zbMATH DE number 2154963
• On maximum bipartite matching with separation
• On bipartite matchings of minimum density
• Maximum semi-matching problem in bipartite graphs
• Approximation by lexicographically maximal solutions in matching and matroid intersection problems
• A semidefinite programming approach to the hypergraph minimum bisection problem

Cites work

• A class of bounded approximation algorithms for graph partitioning
• Approximation algorithms for multi-dimensional assignment problems with decomposable costs
• scientific article; zbMATH DE number 49142 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Performance Guarantees for Approximation Algorithms Depending on Parametrized Triangle Inequalities

Cited in

(2)

• On the traveling salesman problem restricted to inputs satisfying a relaxed triangle inequality
• Odd Minimum Cut Sets and b-Matchings Revisited

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

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