Applying clique-decomposition for computing Gromov hyperbolicity
DOI10.1016/j.tcs.2017.06.001zbMath1371.05284OpenAlexW2601439810MaRDI QIDQ2399620
David Coudert, Aurélien Lancin, Guillaume Ducoffe, Nathann Cohen
Publication date: 24 August 2017
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://hal.inria.fr/hal-01540756/file/CCDL-2017.pdf
Small world graphs, complex networks (graph-theoretic aspects) (05C82) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (6)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Gromov hyperbolic graphs
- Organizing the atoms of the clique separator decomposition into an atom tree
- Distortion of the hyperbolicity constant of a graph
- Hyperbolicity and chordality of a graph
- Into the square: on the complexity of some quadratic-time solvable problems
- Decomposition by clique separators
- Distance-hereditary graphs
- On bridged graphs and cop-win graphs
- Sur les groupes hyperboliques d'après Mikhael Gromov. (On the hyperbolic groups à la M. Gromov)
- On metric properties of certain clique graphs
- Characterizations of outerplanar graphs
- Recognizing quasi-triangulated graphs.
- An introduction to clique minimal separator decomposition
- Hyperbolic bridged graphs
- Computing the Gromov hyperbolicity of a discrete metric space
- Minimal separators of 2-chordal graphs
- Optimal decomposition by clique separators
- Tree-decompositions with bags of small diameter
- On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
- On Computing the Gromov Hyperbolicity
- Tree-Like Structures in Graphs: A Metric Point of View
- Recognition of $C_4$-Free and 1/2-Hyperbolic Graphs
- On Computing the Hyperbolicity of Real-World Graphs
- Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs
- Three Partition Refinement Algorithms
- Decomposition of Directed Graphs
- Algorithmic Aspects of Vertex Elimination on Graphs
- Approximation algorithms for NP-complete problems on planar graphs
- Core congestion is inherent in hyperbolic networks
- Metric Embedding, Hyperbolic Space, and Social Networks
- PARTITION REFINEMENT TECHNIQUES: AN INTERESTING ALGORITHMIC TOOL KIT
- Collective dynamics of ‘small-world’ networks
- Finding Four-Node Subgraphs in Triangle Time
- Transitiv orientierbare Graphen
- Depth-First Search and Linear Graph Algorithms
- SOFSEM 2005: Theory and Practice of Computer Science
- On the hyperbolicity of chordal graphs
This page was built for publication: Applying clique-decomposition for computing Gromov hyperbolicity
