Maximum weighted matching with few edge crossings for 2-layered bipartite graph

DOI10.1016/J.DAM.2020.07.017zbMATH Open1448.05097arXiv1905.04853OpenAlexW3057255635MaRDI QIDQ2004074FDOQ2004074

Authors: Kazuya Haraguchi, Kotaro Torii, Motomu Endo 

Publication date: 14 October 2020

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: Let c denote a non-negative constant. Suppose that we are given an edge-weighted bipartite graph G=(V,E) with its 2-layered drawing and a family X of intersecting edge pairs. We consider the problem of finding a maximum weighted matching M* such that each edge in M* intersects with at most c other edges in M*, and that all edge crossings in M* are contained in X. In the present paper, we propose polynomial-time algorithms for the cases of c=1 and 2. The time complexities of the algorithms are O((k+m)log n+n) for c=1 and O(k^3+k^2n+m(m+log n)) for c=2, respectively, where n=|V|, m=|E| and k=|X|.

Full work available at URL: https://arxiv.org/abs/1905.04853

Recommendations

• Efficient labelling algorithms for the maximum noncrossing matching problem
• Weighted Bipartite Matching in Matrix Multiplication Time
• Crossing Minimization in Weighted Bipartite Graphs
• Crossing minimization in weighted bipartite graphs
• Optimum matchings in weighted bipartite graphs

zbMATH Keywords

edge-weighted bipartite graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Extremal problems in graph theory (05C35) Signed and weighted graphs (05C22) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Introduction to algorithms.
• Priority Search Trees
• Title not available (Why is that?)
• Graph Drawing and Applications for Software and Knowledge Engineers
• The transportation problem with exclusionary side constraints and two branch-and-bound algorithms
• The maximum flow problem with disjunctive constraints
• A branch and cut algorithm for minimum spanning trees under conflict constraints
• Minimum cost noncrossing flow problem on layered networks
• A tabu search heuristic procedure for solving the transportation problem with exclusionary side constraints
• The minimum cost perfect matching problem with conflict pair constraints
• The minimum spanning tree problem with conflict constraints and its variations
• Paths, trees and matchings under disjunctive constraints
• Determining a Minimum Spanning Tree with Disjunctive Constraints
• Stable noncrossing matchings
• A bottleneck matching problem with edge-crossing constraints
• Configurations with few crossings in topological graphs
• Efficient labelling algorithms for the maximum noncrossing matching problem
• Computing maximum non-crossing matching in convex bipartite graphs
• Drawing Bipartite Graphs on Two Parallel Convex Curves

Cited In (5)

• An Optimum Lower Bound for the Weights of Maximum Weight Matching in Bipartite Graphs
• Vertex-Weighted Matching in Two-Directional Orthogonal Ray Graphs
• Crossing Minimization in Weighted Bipartite Graphs
• Efficient labelling algorithms for the maximum noncrossing matching problem
• Crossing minimization in weighted bipartite graphs

This page was built for publication: Maximum weighted matching with few edge crossings for 2-layered bipartite graph

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