On Treewidth and Related Parameters of Random Geometric Graphs
From MaRDI portal
Publication:5270409
DOI10.1137/120874448zbMath1365.05263MaRDI QIDQ5270409
Guillem Perarnau, Dieter Mitsche
Publication date: 23 June 2017
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: http://pure-oai.bham.ac.uk/ws/files/41719294/Mitsche_Perarnau_Treewidth_Related_Parameters_SIAM_Journal_Discrete_Mathematics.pdf
05C80: Random graphs (graph-theoretic aspects)
90B15: Stochastic network models in operations research
05C12: Distance in graphs
05C62: Graph representations (geometric and intersection representations, etc.)
Related Items
Treewidth of the \(q\)-Kneser graphs, On the tree-depth and tree-width in heterogeneous random graphs, Treewidth of the generalized Kneser graphs
Cites Work
- An improved upper bound on the growth constant of polyominoes
- An extension of the Hoeffding inequality to unbounded random variables
- Graph minors. I. Excluding a forest
- S-functions for graphs
- Treewidth. Computations and approximations
- On the order of countable graphs
- Orderings on graphs and game coloring number
- A central limit theorem with applications to percolation, epidemics and Boolean models.
- On the tree-depth of random graphs
- Tree-depth, subgraph coloring and homomorphism bounds
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Rank-width of random graphs
- Sharp thresholds For monotone properties in random geometric graphs
- Graph minors. II. Algorithmic aspects of tree-width
- Random Plane Networks
- Random Geometric Graphs
- Random channel assignment in the plane
- On the treewidth of random geometric graphs and percolated grids
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item