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

DOI10.1080/00207169008803870zbMATH Open0699.68073OpenAlexW2102564932MaRDI QIDQ3477967FDOQ3477967

Authors: 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

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

zbMATH Keywords

diametercenterinterval graphlinear-time algorithm

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• A Characterization of Comparability Graphs and of Interval Graphs
• Title not available (Why is that?)
• Computation of the center and diameter of outerplanar graphs

Cited In (33)

• An optimal algorithm to find centres and diameter of a circular-arc graph
• Algorithms for diameters of unicycle graphs and diameter-optimally augmenting trees
• Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
• Backup 2-center on interval graphs
• Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) time
• Title not available (Why is that?)
• Diameter, eccentricities and distance oracle computations on \(H\)-minor free graphs and graphs of bounded (distance) Vapnik-Chervonenkis dimension
• Modelling gateway placement in wireless networks: geometric \(k\)-centres of unit disc graphs
• 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
• Algorithms for diameters of unicycle graphs and diameter-optimally augmenting trees
• The connected \(p\)-center problem on cactus graphs
• 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
• Fast approximation of eccentricities and distances in hyperbolic graphs
• The connected \(p\)-center problem on block graphs with forbidden vertices
• Optimal sequential and parallel algorithms for computing the diameter and the center of an interval graph
• Beyond Helly graphs: the diameter problem on absolute retracts
• Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
• Fast diameter computation within split graphs
• Distance problems within Helly graphs and \(k\)-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
• Efficient algorithms for centers and medians in interval and circular-arc graphs

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)