Vertex-Weighted Matching in Two-Directional Orthogonal Ray Graphs

DOI10.1007/978-3-642-45030-3_49MaRDI QIDQ2872116zbMATH OpenOpenAlexFDO

Authors C. G. Plaxton

Publication date 14 January 2014

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-45030-3_49

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Deterministic scheduling theory in operations research (90B35) Auctions, bargaining, bidding and selling, and other market models (91B26)

Recommendations

• Matchings in node-weighted convex bipartite graphs
• On orthogonal ray graphs
• Maximum vertex-weighted matching in strongly chordal graphs
• Optimum matchings in weighted bipartite graphs
• Maximum weighted matching with few edge crossings for 2-layered bipartite graph
• A 2/3-approximation algorithm for vertex weighted matching in bipartite graphs
• A \(2/3\)-approximation algorithm for vertex-weighted matching
• Dynamic matchings in left vertex weighted convex bipartite graphs
• A linear-time approximation algorithm for weighted matchings in graphs

Cited in

(4)

• Fast dynamic weight matchings in convex bipartite graphs
• Dynamic matchings in left vertex weighted convex bipartite graphs
• Bipartite matching with linear edge weights
• On orthogonal ray trees

This page was built for publication: Vertex-Weighted Matching in Two-Directional Orthogonal Ray Graphs

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