A note on the independence number, domination number and related parameters of random binary search trees and random recursive trees
From MaRDI portal
Publication:2223687
DOI10.1016/j.dam.2020.12.013OpenAlexW3119903396MaRDI QIDQ2223687
Ralph Neininger, Michael Fuchs, Cecilia Holmgren, Dieter Mitsche
Publication date: 1 February 2021
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1909.12767
independence numberdomination numberclique cover numberrandom binary search treesrandom recursive treesfringe treescentral limit laws
Central limit and other weak theorems (60F05) Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items
On the peel number and the leaf-height of Galton–Watson trees ⋮ Tree evolution processes for bucket increasing trees ⋮ On the distribution of eigenvalues of increasing trees ⋮ The distributions under two species-tree models of the number of root ancestral configurations for matching gene trees and species trees
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Minimum vertex covers and the spectrum of the normalized Laplacian on trees
- Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness
- Bibliography on domination in graphs and some basic definitions of domination parameters
- An analysis of the size of the minimum dominating sets in random recursive trees, using the Cockayne-Goodman-Hedetniemi algorithm
- On maximal independent sets of vertices in claw-free graphs
- Geometric algorithms and combinatorial optimization
- A linear algorithm for the domination number of a tree
- Confining sets and avoiding bottleneck cases: a simple maximum independent set algorithm in degree-3 graphs
- Exact algorithms for maximum independent set
- Local tree-width, excluded minors, and approximation algorithms
- Limit laws for functions of fringe trees for binary search trees and random recursive trees
- Phase Change of Limit Laws in the Quicksort Recurrence under Varying Toll Functions
- A measure & conquer approach for the analysis of exact algorithms
- Inclusion/Exclusion Meets Measure and Conquer
- Algorithms for maximum independent sets
- The Independence Ratio of Regular Graphs
- Linear-time computability of combinatorial problems on series-parallel graphs
- Approximation algorithms for NP-complete problems on planar graphs
- Limit Laws for Sums of Functions of Subtrees of Random Binary Search Trees
- Reducibility among Combinatorial Problems
- Independent Set in P5-Free Graphs in Polynomial Time
