Design, implementation, and analysis of maximum transversal algorithms

DOI10.1145/2049673.2049677MaRDI QIDQ2989152zbMATHOpenAlexWikidataFDO

Authors Kamer Kaya, Bora Uçcar, Iain S. Duff

Publication date 19 May 2017

Published in ACM Transactions on Mathematical Software (Search for Journal in Brave)

Full work available at URL http://purl.org/net/epubs/work/54399

zbMATH Keywords

graph theorymatchingassignmentbipartite graphsbreadth first searchdepth first searchmatrix transversals

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Computational methods for sparse matrices (65F50) Graph algorithms (graph-theoretic aspects) (05C85) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Push-relabel based algorithms for the maximum transversal problem
• Algorithms for finding maximum transitive subtournaments
• Linear-programming design and analysis of fast algorithms for Max 2-CSP
• The design of efficient dynamic programming and transfer matrix enumeration algorithms
• scientific article; zbMATH DE number 1948455
• On complexity of the translational-cut algorithm for convex minimax problems
• On algorithmic construction of maximin distance designs
• An algorithm based on semidefinite programming for finding minimax optimal designs
• Design and analysis of approximation algorithms

Cited in

(5)

• scientific article; zbMATH DE number 7651215 (Why is no real title available?)
• A survey of direct methods for sparse linear systems
• Approximation algorithms in combinatorial scientific computing
• A distributed-memory algorithm for computing a heavy-weight perfect matching on bipartite graphs
• A 2/3-approximation algorithm for vertex weighted matching in bipartite graphs

This page was built for publication: Design, implementation, and analysis of maximum transversal algorithms

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