Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems
From MaRDI portal
Publication:1145508
DOI10.1007/BF00264533zbMath0445.68052MaRDI QIDQ1145508
Franco P. Preparata, Witold jun. Lipski
Publication date: 1981
Published in: Acta Informatica (Search for Journal in Brave)
greedy algorithmsmaximum independent setscheduling algorithmsmaximum matchingsconvex bipartite graphsGale-optimal matching
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)
Related Items
Counting independent sets and maximal independent sets in some subclasses of bipartite graphs ⋮ On-line updating of solutions to a class of matroid intersection problems ⋮ Permuting matrices to avoid forbidden submatrices ⋮ Linear structure of bipartite permutation graphs and the longest path problem ⋮ Circular convex bipartite graphs: Maximum matching and Hamiltonian circuits ⋮ Parallel maximum independent set in convex bipartite graphs ⋮ Dynamic matchings in left vertex weighted convex bipartite graphs ⋮ Variants of Multi-resource Scheduling Problems with Equal Processing Times ⋮ AN OPTIMAL PARALLEL MATCHING ALGORITHM FOR A CONVEX BIPARTITE GRAPH ON A MESH-CONNECTED COMPUTER ⋮ AN OPTIMAL PARALLEL MATCHING ALGORITHM FOR A CONVEX BIPARTITE GRAPH ON A MESH-CONNECTED COMPUTER∗ ⋮ A linear time algorithm for maximum matchings in convex, bipartite graphs ⋮ Fair allocation algorithms for indivisible items under structured conflict constraints ⋮ Routing equal-size messages on a slotted ring ⋮ Probabilistic single processor scheduling ⋮ The maximum deviation just-in-time scheduling problem. ⋮ Optimal computation of shortest paths on doubly convex bipartite graphs ⋮ Matching methods for observational studies derived from large administrative databases ⋮ Solving problems on generalized convex graphs via mim-width ⋮ Efficient parallel algorithms for doubly convex-bipartite graphs ⋮ Finding a manhattan path and related problems ⋮ On complexity of special maximum matchings constructing ⋮ Linear-time algorithm for the paired-domination problem in convex bipartite graphs ⋮ On the complexity of the maximum biplanar subgraph problem ⋮ Scalable parallel algorithms for maximum matching and Hamiltonian circuit in convex bipartite graphs ⋮ NP-completeness results for some problems on subclasses of bipartite and chordal graphs ⋮ Counting preimages of TCP reordering patterns ⋮ Simultaneous consecutive ones submatrix and editing problems: classical complexity and fixed-parameter tractable results ⋮ A fast bipartite network flow algorithm for selective assembly ⋮ On the complexity of the k-chain subgraph cover problem ⋮ Biconvex graphs: Ordering and algorithms ⋮ An 0(n log n) algorithm for the convex bipartite matching problem ⋮ Combinatorial analysis (nonnegative matrices, algorithmic problems) ⋮ A linear-time algorithm for a special case of disjoint set union ⋮ Computing maximum non-crossing matching in convex bipartite graphs ⋮ Optimal point movement for covering circular regions
