On the k-orientability of random graphs

DOI10.1016/J.DISC.2008.02.023zbMATH Open1227.05227OpenAlexW2139277171MaRDI QIDQ1024456FDOQ1024456

Authors Ebrahim Malalla, Luc 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

competitive analysisrandom graphs\(k\)-coreprobabilistic analysis of algorithmsmaximum density\(k\)-orientabilityOff-line load balancingstatic two-way chaining

Mathematics Subject Classification ID

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

Recommendations

• The \(k\)-orientability thresholds for \(G_{n,p}\)
• Orientability of random hypergraphs and the power of multiple choices
• The multiple-orientability thresholds for random hypergraphs
• The Multiple-Orientability Thresholds for Random Hypergraphs
• Orientability Thresholds for Random Hypergraphs

Cites work

• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 4170917 (Why is no real title available?)
• scientific article; zbMATH DE number 3727273 (Why is no real title available?)
• scientific article; zbMATH DE number 3548141 (Why is no real title available?)
• scientific article; zbMATH DE number 3604926 (Why is no real title available?)
• scientific article; zbMATH DE number 1301967 (Why is no real title available?)
• scientific article; zbMATH DE number 1025912 (Why is no real title available?)
• scientific article; zbMATH DE number 1146228 (Why is no real title available?)
• scientific article; zbMATH DE number 2079854 (Why is no real title available?)
• scientific article; zbMATH DE number 1775423 (Why is no real title available?)
• scientific article; zbMATH DE number 1857645 (Why is no real title available?)
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Balanced Allocations
• Balanced Allocations: The Heavily Loaded Case
• Balanced allocation and dictionaries with tightly packed constant size bins
• Expected Length of the Longest Probe Sequence in Hash Code Searching
• How asymmetry helps load balancing
• On the cell probe complexity of membership and perfect hashing
• On the orientation of graphs
• On-line load balancing
• Randomized allocation processes
• Routing on networks of optical crossbars
• Some inequalities relating to the partial sum of binomial probabilities
• Sudden emergence of a giant \(k\)-core in a random graph
• The Competitiveness of On-Line Assignments
• The birth of the giant component
• Two-Way Chaining with Reassignment

Cited in

(7)

• Characterization of randomly \(k\)-dimensional graphs.
• Counting restricted orientations of random graphs
• A new approach to the orientation of random hypergraphs
• Orientability Thresholds for Random Hypergraphs
• Graphs with many strong orientations
• The \(k\)-orientability thresholds for \(G_{n,p}\)
• The Multiple-Orientability Thresholds for Random Hypergraphs

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

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