Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems

DOI10.1007/BF00264533MaRDI QIDQ1145508zbMATH OpenFDO

Authors Witold jun. Lipski, F. P. Preparata

Publication date 1981

Published in Acta Informatica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF00264533

zbMATH Keywords

convex bipartite graphsGale-optimal matchinggreedy algorithmsmaximum independent setmaximum matchingsscheduling algorithms

Mathematics Subject Classification ID

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) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cited in

(37)

• Counting preimages of TCP reordering patterns
• Combinatorial analysis (nonnegative matrices, algorithmic problems)
• A linear-time algorithm for a special case of disjoint set union
• On-line updating of solutions to a class of matroid intersection problems
• A fast bipartite network flow algorithm for selective assembly
• On the complexity of the k-chain subgraph cover problem
• Circular convex bipartite graphs: Maximum matching and Hamiltonian circuits
• Parallel maximum independent set in convex bipartite graphs
• The maximum deviation just-in-time scheduling problem.
• Biconvex graphs: Ordering and algorithms
• Counting independent sets and maximal independent sets in some subclasses of bipartite graphs
• Permuting matrices to avoid forbidden submatrices
• A linear time algorithm for maximum matchings in convex, bipartite graphs
• Optimal computation of shortest paths on doubly convex bipartite graphs
• Matching methods for observational studies derived from large administrative databases
• Scalable parallel algorithms for maximum matching and Hamiltonian circuit in convex bipartite graphs
• Simultaneous consecutive ones submatrix and editing problems: classical complexity and fixed-parameter tractable results
• Computing maximum non-crossing matching in convex bipartite graphs
• Linear structure of bipartite permutation graphs and the longest path problem
• Routing equal-size messages on a slotted ring
• Dynamic matchings in left vertex weighted convex bipartite graphs
• Finding a manhattan path and related problems
• 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∗
• On the complexity of the maximum biplanar subgraph problem
• Fair allocation algorithms for indivisible items under structured conflict constraints
• Solving problems on generalized convex graphs via mim-width
• Approximation hardness of domination problems on generalized convex graphs
• Efficient parallel algorithms for doubly convex-bipartite graphs
• Boundedness for proper conflict-free and odd colorings
• Linear-time algorithm for the paired-domination problem in convex bipartite graphs
• Connected partitions via connected dominating sets
• An 0(n log n) algorithm for the convex bipartite matching problem
• Probabilistic single processor scheduling
• On complexity of special maximum matchings constructing
• NP-completeness results for some problems on subclasses of bipartite and chordal graphs

This page was built for publication: Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems

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