A faster diameter problem algorithm for a chordal graph, with a connection to its center problem
From MaRDI portal
Publication:2659238
DOI10.1016/j.disc.2021.112326OpenAlexW3130864778MaRDI QIDQ2659238
Publication date: 25 March 2021
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disc.2021.112326
Algorithms in computer science (68Wxx) Theory of computing (68Qxx) Graph theory (05Cxx) Discrete mathematics in relation to computer science (68Rxx)
Cites Work
- Unnamed Item
- Unnamed Item
- On computing the diameter of real-world undirected graphs
- Into the square: on the complexity of some quadratic-time solvable problems
- Computation of the center and diameter of outerplanar graphs
- LexBFS-orderings and powers of chordal graphs
- Which problems have strongly exponential complexity?
- Computing the eccentricity distribution of large graphs
- Fast diameter computation within split graphs
- Fast diameter and radius BFS-based computation in (weakly connected) real-world graphs
- A simple linear-time algorithm for computing the center of an interval graph
- The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
- Centers of 2–Trees
- Algorithmic Aspects of Vertex Elimination on Graphs
- Graph Classes: A Survey
- Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
- Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
- Fast approximation algorithms for the diameter and radius of sparse graphs
- On the complexity of \(k\)-SAT
- Diameter determination on restricted graph families
This page was built for publication: A faster diameter problem algorithm for a chordal graph, with a connection to its center problem
