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

DOI10.7151/DMGT.1758MaRDI QIDQ2509535zbMATH OpenOpenAlexFDO

Authors Kunal Dutta, C. R. Subramanian

Publication date 28 July 2014

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

Copyright license Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported

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

zbMATH Keywords

algorithmsconcentrationrandom digraphsthresholdstournaments

Mathematics Subject Classification ID

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

Recommendations

• Largest induced acyclic tournament in random digraphs: a 2-point concentration
• Improved bounds on induced acyclic subgraphs in random digraphs
• Induced acyclic subgraphs in random digraphs: improved bounds
• On the size of induced acyclic subgraphs in random digraphs
• On induced acyclic subgraphs in sparse random digraphs

Cites work

• A note on the sharp concentration of the chromatic number of random graphs
• An approximation algorithm for feedback vertex sets in tournaments
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Cliques in random graphs
• Coloring random graphs
• Finding induced acyclic subgraphs in random digraphs
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 219267 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• scientific article; zbMATH DE number 3302923 (Why is no real title available?)
• Induced acyclic subgraphs in random digraphs: improved bounds
• Largest induced acyclic tournament in random digraphs: a 2-point concentration
• On the independence number of random graphs
• On the size of induced acyclic subgraphs in random digraphs
• Optimization, approximation, and complexity classes
• Random graphs.
• Robust linear algorithms for cutsets
• The approximation of maximum subgraph problems
• The concentration of the chromatic number of random graphs
• The probabilistic method
• The two possible values of the chromatic number of a random graph

Cited in

(12)

• Finding induced acyclic subgraphs in random digraphs
• On the evolution of a random tournament
• Improved bounds on induced acyclic subgraphs in random digraphs
• On induced acyclic subgraphs in sparse random digraphs
• Induced acyclic subgraphs in random digraphs: improved bounds
• Largest induced acyclic tournament in random digraphs: a 2-point concentration
• On the size of induced acyclic subgraphs in random digraphs
• On high-dimensional acyclic tournaments
• scientific article; zbMATH DE number 1334601 (Why is no real title available?)
• scientific article; zbMATH DE number 1984544 (Why is no real title available?)
• Economic genome assembly from low coverage illumina and nanopore data
• On the maximum cardinality of a consistent set of arcs in a random tournament

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

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