Algorithms for dense graphs and networks on the random access computer

DOI10.1007/BF01940880zbMath0848.68070WikidataQ55952576 ScholiaQ55952576MaRDI QIDQ1918989

Kurt Mehlhorn, Joseph Cheriyan

Publication date: 21 October 1996

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

assignment problemnetwork algorithmsdense graphs

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Linear-Time Approximation for Maximum Weight Matching, A parallel algorithm for GAC filtering of the Alldifferent constraint, Speeding up Graph Algorithms via Switching Classes, Finding all maximally-matchable edges in a bipartite graph, An \(n\log n\) algorithm for hyper-minimizing a (minimized) deterministic automaton, A simple reduction from maximum weight matching to maximum cardinality matching, On the complexity of strongly connected components in directed hypergraphs, An nlogn Algorithm for Hyper-minimizing States in a (Minimized) Deterministic Automaton, Unnamed Item, Unnamed Item

Uses Software

• LEDA

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)
• Upper bounds for sorting integers on random access machines
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• A strong-connectivity algorithm and its applications in data flow analysis
• Finding minimum-cost flows by double scaling
• New scaling algorithms for the assignment and minimum mean cycle problems
• Clique partitions, graph compression and speeding-up algorithms
• Some Recent Advances in Network Flows
• A new algorithm for the assignment problem
• Scan-First Search and Sparse Certificates: An Improved Parallel Algorithm for k-Vertex Connectivity
• Faster Scaling Algorithms for Network Problems
• Depth-First Search and Linear Graph Algorithms
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs