scientific article; zbMATH DE number 1431747
A geometric bipartite graph \(G=(V,E)\) is defined in the article as a graph whose vertices are points on the plain such that \(V = X \cup Y\), where sets \(X\) and \(Y\) lie on two parallel lines, and edges are segments \(E \subseteq \{[x,y]\mid x \in X\) and \(y \in Y \}\). A subset \(M\) of \(E\) is a geometric matching in G if the segments in \(M\) are pairwise disjoint. A graph \(G=(X \cup Y,E)\) is said to have a canonical form if \(|X|=|Y|=|E|\) and all vertices are of degree one. Thus, a canonical geometric bipartite graph is equivalent to a permutation graph, and matching problems on canonical geometric bipartite graphs correspond to problems on permutation graphs. The author considers four natural problems on geometric matchings (in particular, the maximum geometric matching problem) in geometric bipartite weighted graphs. Effective algorithms for solving these problems are given and discussed.
- Bipartite matching and Van der Waerden conjecture
- scientific article; zbMATH DE number 95268 (Why is no real title available?)
- Complete Description of Matching Polytopes with One Linearized Quadratic Term for Bipartite Graphs
- Partitions of complete bipartite geometric graphs into plane perfect matchings
- A geometric theory for hypergraph matching
- Maximum matchings in geometric intersection graphs
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4948670)
