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

DOI10.1080/00207169008803870zbMath0699.68073OpenAlexW2102564932MaRDI QIDQ3477967

Stephan Olariu

Publication date: 1990

Published in: International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/00207169008803870

zbMATH Keywords

centerdiameterinterval graphlinear-time algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (26)

Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs ⋮ Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension ⋮ The connected \(p\)-center problem on cactus graphs ⋮ Efficient algorithms for centers and medians in interval and circular-arc graphs ⋮ An improved algorithm for the \(p\)-center problem on interval graphs with unit lengths ⋮ A faster diameter problem algorithm for a chordal graph, with a connection to its center problem ⋮ On minimum intersection of two minimum dominating sets of interval graphs ⋮ Beyond Helly graphs: the diameter problem on absolute retracts ⋮ The diameter of AT‐free graphs ⋮ Streaming deletion problems Parameterized by vertex cover ⋮ A story of diameter, radius, and (almost) Helly property ⋮ Computation of diameter, radius and center of permutation graphs ⋮ Distance problems within Helly graphs and \(k\)-Helly graphs ⋮ The Connected p-Center Problem on Cactus Graphs ⋮ The connected \(p\)-center problem on block graphs with forbidden vertices ⋮ Finding a central vertex in an HHD-free graph ⋮ Optimal sequential and parallel algorithms for computing the diameter and the center of an interval graph ⋮ Backup 2-center on interval graphs ⋮ Modelling gateway placement in wireless networks: geometric \(k\)-centres of unit disc graphs ⋮ Diameter determination on restricted graph families ⋮ Algorithms for diameters of unicycle graphs and diameter-optimally augmenting trees ⋮ Fast approximation of eccentricities and distances in hyperbolic graphs ⋮ Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic $\tilde{O}(n^{5/3})$ Time ⋮ Graph Pattern Detection: Hardness for all Induced Patterns and Faster Noninduced Cycles ⋮ Algorithms for diameters of unicycle graphs and diameter-optimally augmenting trees ⋮ Fast Diameter Computation within Split Graphs

Cites Work

• Computation of the center and diameter of outerplanar graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• A Characterization of Comparability Graphs and of Interval Graphs
• Unnamed Item
• Unnamed Item

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