The diameter of AT‐free graphs
From MaRDI portal
Publication:6057658
DOI10.1002/jgt.22754zbMath1522.05466arXiv2010.15814MaRDI QIDQ6057658
Publication date: 5 October 2023
Published in: Journal of Graph Theory (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2010.15814
Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)
Related Items (2)
Computing and listing avoidable vertices and paths ⋮ Computing and listing avoidable vertices and paths
Cites Work
- Unnamed Item
- Line-distortion, bandwidth and path-length of a graph
- End-vertices of LBFS of (AT-free) bigraphs
- Into the square: on the complexity of some quadratic-time solvable problems
- On the all-pairs-shortest-path problem in unweighted undirected graphs.
- Almost diameter of a house-hole-free graph in linear time via LexBFS
- Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
- On claw-free asteroidal triple-free graphs
- Fast diameter computation within split graphs
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- A new algorithm for optimal 2-constraint satisfaction and its implications
- Graphs with Connected Medians
- Linear-time graph distance and diameter approximation
- Representation of a finite graph by a set of intervals on the real line
- BetweenO(nm) andO(nalpha)
- A simple linear-time algorithm for computing the center of an interval graph
- Algorithmic Aspects of Vertex Elimination on Graphs
- The leafage of a chordal graph
- Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free Graphs
- Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
- An Axiomatic and an Average-Case Analysis of Algorithms and Heuristics for Metric Properties of Graphs
- Subcubic Equivalences Between Path, Matrix, and Triangle Problems
- Subquadratic Algorithms for the Diameter and the Sum of Pairwise Distances in Planar Graphs
- Dominating Pair Graphs
- Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs
- Diameter computation on H-minor free graphs and graphs of bounded (distance) VC-dimension
- Cop and Robber Game and Hyperbolicity
- Slimness of graphs
- Fast approximation algorithms for the diameter and radius of sparse graphs
- On the structure of graphs with bounded asteroidal number
- On the complexity of \(k\)-SAT
- Diameter determination on restricted graph families
This page was built for publication: The diameter of AT‐free graphs
