An improved Boolean circuit for maximum matching in a convex bipartite graph

MaRDI QIDQ5506330zbMATH OpenFDO

Authors Eunhui Park, Kunsoo Park

Publication date 28 January 2009

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Scalable parallel algorithms for maximum matching and Hamiltonian circuit in convex bipartite graphs
• Parallel maximum independent set in convex bipartite graphs
• Computing maximum non-crossing matching in convex bipartite graphs
• Circular convex bipartite graphs: Maximum matching and Hamiltonian circuits
• A linear time algorithm for maximum matchings in convex, bipartite graphs

Cited in

(4)

• Boolean circuit programming: A new paradigm to design parallel algorithms
• A new pairwise NPN Boolean matching algorithm based on structural difference signature
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• Linear-time algorithm for the paired-domination problem in convex bipartite graphs

This page was built for publication: An improved Boolean circuit for maximum matching in a convex bipartite graph

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