A note on the independence number, domination number and related parameters of random binary search trees and random recursive trees

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

zbMATH Keywords

independence numberdomination numberclique cover numberrandom binary search treesrandom recursive treesfringe treescentral limit laws

Mathematics Subject Classification ID

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 P₅-Free Graphs in Polynomial Time