On the \(k\)-orientability of random graphs

DOI10.1016/j.disc.2008.02.023zbMath1227.05227OpenAlexW2139277171MaRDI QIDQ1024456

Ebrahim Malalla, Luc P. Devroye

Publication date: 17 June 2009

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

Full work available at URL: https://doi.org/10.1016/j.disc.2008.02.023

zbMATH Keywords

random graphscompetitive analysisprobabilistic analysis of algorithms\(k\)-coremaximum density\(k\)-orientabilityOff-line load balancingstatic two-way chaining

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Some inequalities relating to the partial sum of binomial probabilities
• Routing on networks of optical crossbars
• On the orientation of graphs
• On-line load balancing
• Sudden emergence of a giant \(k\)-core in a random graph
• Balanced allocation and dictionaries with tightly packed constant size bins
• Randomized allocation processes
• How asymmetry helps load balancing
• Expected Length of the Longest Probe Sequence in Hash Code Searching
• Balanced Allocations
• The Competitiveness of On-Line Assignments
• On the cell probe complexity of membership and perfect hashing
• The birth of the giant component
• Two-Way Chaining with Reassignment
• Balanced Allocations: The Heavily Loaded Case
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs

This page was built for publication: On the \(k\)-orientability of random graphs