Dynamic Matchings in Convex Bipartite Graphs

DOI10.1007/978-3-540-74456-6_37MaRDI QIDQ3525588zbMATH OpenOpenAlexFDO

Authors Gerth Stølting Brodal, Loukas Georgiadis, Kristoffer Arnsfelt Hansen, Irit Katriel

Publication date 17 September 2008

Published in Mathematical Foundations of Computer Science 2007 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-74456-6_37

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Dynamic Matchings in Left Weighted Convex Bipartite Graphs
• Fast dynamic weight matchings in convex bipartite graphs
• Dynamic matchings in left vertex weighted convex bipartite graphs
• Fully dynamic matching in bipartite graphs
• Fully dynamic maximal matching in O( n) update time

Cited in

(10)

• Finding maximum edge bicliques in convex bipartite graphs
• Scalable parallel algorithms for maximum matching and Hamiltonian circuit in convex bipartite graphs
• Faster dynamic matchings and vertex connectivity
• Fast dynamic weight matchings in convex bipartite graphs
• Dynamic Matchings in Left Weighted Convex Bipartite Graphs
• Dynamic matchings in left vertex weighted convex bipartite graphs
• Total domination and open packing in some subclasses of bipartite graphs
• Happy set problems on cubic graphs and convex bipartite graphs
• Linear-time algorithm for the paired-domination problem in convex bipartite graphs
• Connected partitions via connected dominating sets

This page was built for publication: Dynamic Matchings in Convex Bipartite Graphs

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