A simple linear-time algorithm for computing the center of an interval graph

Recommendations

Optimal sequential and parallel algorithms for computing the diameter and the center of an interval graph
scientific article; zbMATH DE number 1670650
An optimal algorithm to find centres and diameter of a circular-arc graph
An improved algorithm for the p-center problem on interval graphs with unit lengths
Efficient algorithms for centers and medians in interval and circular-arc graphs

Cites work

scientific article; zbMATH DE number 3859178 (Why is no real title available?)
scientific article; zbMATH DE number 3706451 (Why is no real title available?)
A Characterization of Comparability Graphs and of Interval Graphs
Computation of the center and diameter of outerplanar graphs
Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms

Cited in

(33)

Efficient algorithms for centers and medians in interval and circular-arc graphs
An optimal algorithm to find centres and diameter of a circular-arc graph
Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
Algorithms for diameters of unicycle graphs and diameter-optimally augmenting trees
Backup 2-center on interval graphs
scientific article; zbMATH DE number 1670650 (Why is no real title available?)
Voronoi diagrams on planar graphs, and computing the diameter in deterministic $\tilde{O}(n^{5/3})$ time
Modelling gateway placement in wireless networks: geometric $k$-centres of unit disc graphs
Diameter, eccentricities and distance oracle computations on $H$-minor free graphs and graphs of bounded (distance) Vapnik-Chervonenkis dimension
Finding a central vertex in an HHD-free graph
The connected $p$-center problem on cactus graphs
Diameter determination on restricted graph families
$ \alpha_i$-metric graphs: radius, diameter and all eccentricities
A story of diameter, radius, and (almost) Helly property
An improved algorithm for the p-center problem on interval graphs with unit lengths
The connected $p$-center problem on cactus graphs
Algorithms for diameters of unicycle graphs and diameter-optimally augmenting trees
Graph pattern detection: hardness for all induced patterns and faster noninduced cycles
The diameter of AT‐free graphs
A faster diameter problem algorithm for a chordal graph, with a connection to its center problem
A linear time deterministic algorithm to find a small subset that approximates the centroid
The connected p-center problem on block graphs with forbidden vertices
Fast approximation of eccentricities and distances in hyperbolic graphs
Beyond Helly graphs: the diameter problem on absolute retracts
Optimal sequential and parallel algorithms for computing the diameter and the center of an interval graph
Distance problems within Helly graphs and $k$-Helly graphs
Fast diameter computation within split graphs
Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
$$\alpha _i$$-Metric Graphs: Radius, Diameter and all Eccentricities
On minimum intersection of two minimum dominating sets of interval graphs
Computation of diameter, radius and center of permutation graphs
A polynomial time algorithm for finding the absolute center of a network
Streaming deletion problems Parameterized by vertex cover

This page was built for publication: A simple linear-time algorithm for computing the center of an interval graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3477967)