scientific article; zbMATH DE number 7378590

DOI10.4230/LIPIcs.IPEC.2018.4MaRDI QIDQ5009466

Thore Husfeldt, Måns Magnusson, Karl Bringmann

Publication date: 4 August 2021

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

diametertreewidthradiusWiener indexvertex cover numberorthogonal range searching

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68Wxx)

Related Items (2)

Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs ⋮ Fast Diameter Computation within Split Graphs

Cites Work

• Multidimensional divide-and-conquer
• Algorithms for graphs of bounded treewidth via orthogonal range searching
• Which problems have strongly exponential complexity?
• All-pairs shortest paths with real weights in \(O ( n^{3}/\log n )\) time
• A $c^k n$ 5-Approximation Algorithm for Treewidth
• Lower bounds for orthogonal range searching: I. The reporting case
• New Data Structures for Orthogonal Range Queries
• Combinatorial solutions of multidimensional divide-and-conquer recurrences
• Quintary trees
• Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
• Computing Graph Distances Parameterized by Treewidth and Diameter
• Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
• Fast approximation algorithms for the diameter and radius of sparse graphs
• Parameterized complexity of diameter

This page was built for publication: