Tree decompositions and social graphs
From MaRDI portal
Publication:5856440
DOI10.1080/15427951.2016.1182952zbMath1461.68139arXiv1411.1546OpenAlexW2963079722WikidataQ57434415 ScholiaQ57434415MaRDI QIDQ5856440
Michael W. Mahoney, Aaron Adcock, Blair D. Sullivan
Publication date: 26 March 2021
Published in: Internet Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1411.1546
Social networks; opinion dynamics (91D30) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
Related Items
The hyperbolicity constant of infinite circulant graphs ⋮ On Treewidth and Stable Marriage: Parameterized Algorithms and Hardness Results (Complete Characterization) ⋮ Helly-gap of a graph and vertex eccentricities ⋮ Local 2-separators ⋮ Eccentricity terrain of \(\delta\)-hyperbolic graphs ⋮ On the herdability of linear time-invariant systems with special topological structures ⋮ Maximizing the strong triadic closure in split graphs and proper interval graphs ⋮ Graph theory. Abstracts from the workshop held January 2--8, 2022 ⋮ To Approximate Treewidth, Use Treelength! ⋮ An Experimental Study of the Treewidth of Real-World Graph Data ⋮ From Graph Theory to Network Science: The Natural Emergence of Hyperbolicity (Tutorial) ⋮ Unnamed Item
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Treewidth of Erdős-Rényi random graphs, random intersection graphs, and scale-free random graphs
- Hyperbolicity and chordality of a graph
- Monadic second-order evaluations on tree-decomposable graphs
- Connected tree-width
- Minimal triangulations of graphs: a survey
- Approximation algorithms for treewidth
- \(k\)-core decomposition of internet graphs: hierarchies, self-similarity and measurement biases
- Treewidth computations. I: Upper bounds
- On compact and efficient routing in certain graph classes
- The analysis of a nested dissection algorithm
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Call routing and the ratcatcher
- On treewidth approximations.
- Maximum cardinality search for computing minimal triangulations of graphs
- Scaled Gromov four-point condition for network graph curvature computation
- Tree-decompositions with bags of small diameter
- Geodetic topological cycles in locally finite graphs
- Fast algorithms for determining (generalized) core groups in social networks
- On tree width, bramble size, and expansion
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- The Elimination form of the Inverse and its Application to Linear Programming
- On the Hyperbolicity of Small-World and Treelike Random Graphs
- Tree-Like Structures in Graphs: A Metric Point of View
- The university of Florida sparse matrix collection
- Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters
- k-Chordal Graphs: From Cops and Robber to Compact Routing via Treewidth
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Characterization of Graphs Using Degree Cores
- Treewidth: Characterizations, Applications, and Computations
- On the Complexity of Computing Treelength
- Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs
- The peculiar phase structure of random graph bisection
- Addendum: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Graph minors. II. Algorithmic aspects of tree-width
- Algorithmic Aspects of Vertex Elimination on Graphs
- A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
- Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
- Metric Embedding, Hyperbolic Space, and Social Networks
- The Pathwidth and Treewidth of Cographs
- An Approximate Minimum Degree Ordering Algorithm
- Linear-time computation of optimal subgraphs of decomposable graphs
- Solving partial constraint satisfaction problems with tree decomposition
- An open graph visualization system and its applications to software engineering
- Efficient Parallel Algorithms for Graphs of Bounded Tree-Width
- A Note on Treewidth in Random Graphs
- Polynomial bounds for the grid-minor theorem
- Collective dynamics of ‘small-world’ networks
- Core-Periphery Structure in Networks
- Scaled Gromov hyperbolic graphs
- Algorithm 837
- Nested Dissection of a Regular Finite Element Mesh
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- SOFSEM 2005: Theory and Practice of Computer Science
- Graph-Theoretic Concepts in Computer Science
- On the hyperbolicity of chordal graphs
- A sufficiently fast algorithm for finding close to optimal clique trees
