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

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

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)

Cites Work

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

Cited In (6)

• Counting restricted orientations of random graphs
• Characterization of randomly \(k\)-dimensional graphs.
• The \(k\)-orientability thresholds for \(G_{n,p}\)
• Orientability Thresholds for Random Hypergraphs
• A new approach to the orientation of random hypergraphs
• 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)