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

DOI10.1016/J.DAM.2020.07.017MaRDI QIDQ2004074zbMATH OpenOpenAlexFDO

Authors Kazuya Haraguchi, Kotaro Torii, Motomu Endo

Publication date 14 October 2020

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

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

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)

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|.

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

Cites work

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

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)