Obstructions to faster diameter computation: asteroidal sets
From MaRDI portal
Cites work
- scientific article; zbMATH DE number 4031953 (Why is no real title available?)
- scientific article; zbMATH DE number 1107735 (Why is no real title available?)
- scientific article; zbMATH DE number 2119682 (Why is no real title available?)
- scientific article; zbMATH DE number 7788370 (Why is no real title available?)
- 3-colouring AT-free graphs in polynomial time
- A linear time algorithm to compute a dominating path in an AT-free graph
- A new application of orthogonal range searching for computing giant graph diameters
- A simple linear-time algorithm for computing the center of an interval graph
- A story of diameter, radius, and (almost) Helly property
- AT-free graphs: Linear bounds for the oriented diameter
- Absolute retracts of bipartite graphs
- Algorithmic Aspects of Vertex Elimination on Graphs
- Algorithmic graph theory and perfect graphs
- Algorithms for graphs of bounded treewidth via orthogonal range searching
- An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs
- An axiomatic and an average-case analysis of algorithms and heuristics for metric properties of graphs
- Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
- Asteroidal Triple-Free Graphs
- Asteroidal triples of moplexes
- Bandwidth on AT-free graphs
- BetweenO(nm) andO(nalpha)
- Beyond Helly graphs: the diameter problem on absolute retracts
- Characterising AT-free graphs with BFS
- Colouring AT-free graphs
- Computation of the center and diameter of outerplanar graphs
- Covering planar graphs with a fixed number of balls
- Diameter computation on H-minor free graphs and graphs of bounded (distance) VC-dimension
- Diameter determination on restricted graph families
- Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs
- Efficient characterizations of \(n\)-chromatic absolute retracts
- End-vertices of LBFS of (AT-free) bigraphs
- Fast approximation algorithms for the diameter and radius of sparse graphs
- Fast approximation of eccentricities and distances in hyperbolic graphs
- Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
- Feedback vertex set on AT-free graphs
- Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
- Graph theory
- Graphs with two moplexes
- Hereditary dominating pair graphs
- Independent Sets in Asteroidal Triple-Free Graphs
- Induced disjoint paths in AT-free graphs
- Isometric embeddings in trees and their use in distance problems
- Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
- LexBFS-orderings and powers of graphs
- LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem
- Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free Graphs
- Network Analysis
- On claw-free asteroidal triple-free graphs
- On polygon numbers of circle graphs and distance hereditary graphs
- On powers and centers of chordal graphs
- On the all-pairs-shortest-path problem in unweighted undirected graphs.
- On the complexity of k-SAT
- On the power of BFS to determine a graph's diameter
- On the structure of graphs with bounded asteroidal number
- Optimal centrality computations within bounded clique-width graphs
- Polynomial-time algorithms for weighted efficient domination problems in AT-free graphs and dually chordal graphs
- Separability generalizes Dirac's theorem
- Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
- Subcubic equivalences between path, matrix, and triangle problems
- Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs
- The algorithmic use of hypertree structure and maximum neighbourhood orderings
- The diameter of AT‐free graphs
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- The leafage of a chordal graph
- Three Partition Refinement Algorithms
- Transitiv orientierbare Graphen
- VC-dimension and Erdős-Pósa property
- Vertex ordering characterizations of graphs of bounded asteroidal number
- Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) time
Cited in
(2)
This page was built for publication: Obstructions to faster diameter computation: asteroidal sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6969002)
