When can graph hyperbolicity be computed in linear time?

DOI10.1007/s00453-018-0522-6zbMath1439.68016OpenAlexW2897727262MaRDI QIDQ5915992

Till Fluschnik, Nimrod Talmon, George B. Mertzios, Rolf Niedermeier, Christian Komusiewicz, André Nichterlein

Publication date: 7 May 2019

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: http://dro.dur.ac.uk/26316/1/26316.pdf

zbMATH Keywords

polynomial-time algorithmcographsparameterized complexityvertex cover numberstrong exponential time hypothesisFPT in P

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (2)

A fully polynomial parameterized algorithm for counting the number of reachable vertices in a digraph ⋮ Parameterized complexity of diameter

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the hyperbolicity of random graphs
• A survey of the algorithmic aspects of modular decomposition
• On the complexity of fixed parameter clique and dominating set
• Into the square: on the complexity of some quadratic-time solvable problems
• On the parameterized complexity of multiple-interval graph problems
• Complement reducible graphs
• Which problems have strongly exponential complexity?
• Hyperbolic bridged graphs
• Computing the Gromov hyperbolicity of a discrete metric space
• Applying clique-decomposition for computing Gromov hyperbolicity
• Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs
• On Computing the Gromov Hyperbolicity
• Cluster Vertex Deletion: A Parameterization between Vertex Cover and Clique-Width
• Recognition of $C_4$-Free and 1/2-Hyperbolic Graphs
• Integer Programming with a Fixed Number of Variables
• On Computing the Hyperbolicity of Real-World Graphs
• A Linear Recognition Algorithm for Cographs
• Graph Classes: A Survey
• Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
• An Adaptive Version of Brandes' Algorithm for Betweenness Centrality
• The Power of Linear-Time Data Reduction for Maximum Matching
• Finding Four-Node Subgraphs in Triangle Time
• Finding orthogonal vectors in discrete structures
• On the hyperbolicity of chordal graphs
• On the complexity of \(k\)-SAT

This page was built for publication: When can graph hyperbolicity be computed in linear time?