Induced acyclic tournaments in random digraphs: sharp concentration, thresholds and algorithms

DOI10.7151/dmgt.1758zbMath1295.05209OpenAlexW1967447889MaRDI QIDQ2509535

Kunal Dutta, C. R. Subramanian

Publication date: 28 July 2014

Published in: Discussiones Mathematicae. Graph Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.7151/dmgt.1758

zbMATH Keywords

algorithmsthresholdstournamentsconcentrationrandom digraphs

Mathematics Subject Classification ID

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
• Coloring random graphs
• On the independence number of random graphs
• A note on the sharp concentration of the chromatic number of random graphs
• Optimization, approximation, and complexity classes
• The concentration of the chromatic number of random graphs
• Finding induced acyclic subgraphs in random digraphs
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• An Approximation Algorithm for Feedback Vertex Sets in Tournaments
• Largest Induced Acyclic Tournament in Random Digraphs: A 2-Point Concentration
• Robust linear algorithms for cutsets
• Cliques in random graphs
• The approximation of maximum subgraph problems
• The two possible values of the chromatic number of a random graph

This page was built for publication: Induced acyclic tournaments in random digraphs: sharp concentration, thresholds and algorithms