Into the square: on the complexity of some quadratic-time solvable problems

DOI10.1016/j.entcs.2016.03.005zbMath1345.68170arXiv1407.4972OpenAlexW1499093134WikidataQ113317700 ScholiaQ113317700MaRDI QIDQ737085

Michele Borassi, Pierluigi Crescenzi, Michel A. Habib

Publication date: 5 August 2016

Full work available at URL: https://arxiv.org/abs/1407.4972

zbMATH Keywords

reductionstransitive closurequadratic-time algorithmsstrong exponential-time hypothesis

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (23)

Matching Triangles and Basing Hardness on an Extremely Popular Conjecture ⋮ Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs ⋮ Computing the union join and subset graph of acyclic hypergraphs in subquadratic time ⋮ Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension ⋮ A note on the complexity of computing the number of reachable vertices in a digraph ⋮ Applying clique-decomposition for computing Gromov hyperbolicity ⋮ Eccentricity queries and beyond using hub labels ⋮ A faster diameter problem algorithm for a chordal graph, with a connection to its center problem ⋮ Fast approximation and exact computation of negative curvature parameters of graphs ⋮ Beyond Helly graphs: the diameter problem on absolute retracts ⋮ A general algorithmic scheme for combinatorial decompositions with application to modular decompositions of hypergraphs ⋮ The diameter of AT‐free graphs ⋮ A story of diameter, radius, and (almost) Helly property ⋮ Unnamed Item ⋮ On computing large temporal (unilateral) connected components ⋮ Revisiting Decomposition by Clique Separators ⋮ When can graph hyperbolicity be computed in linear time? ⋮ Non-inclusion and other subclasses of chordal graphs ⋮ Into the square: on the complexity of some quadratic-time solvable problems ⋮ Fast approximation of eccentricities and distances in hyperbolic graphs ⋮ Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs ⋮ Fast Approximation and Exact Computation of Negative Curvature Parameters of Graphs ⋮ Fast Diameter Computation within Split Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On computing the diameter of real-world undirected graphs
• Hyperbolicity and chordality of a graph
• Into the square: on the complexity of some quadratic-time solvable problems
• Modular decomposition and transitive orientation
• Finding extremal sets in less than quadratic time
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• Which problems have strongly exponential complexity?
• Subquadratic algorithms for 3SUM
• A new algorithm for optimal 2-constraint satisfaction and its implications
• A faster algorithm for betweenness centrality*
• On Computing the Gromov Hyperbolicity
• Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs
• Finding a Minimum Circuit in a Graph
• The Structure and Function of Complex Networks
• Threesomes, Degenerates, and Love Triangles
• Reducibility among Combinatorial Problems
• Consequences of Faster Alignment of Sequences
• The Subset Partial Order: Computing and Combinatorics
• Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter
• Finding orthogonal vectors in discrete structures
• Approximating Betweenness Centrality
• Fast approximation algorithms for the diameter and radius of sparse graphs

This page was built for publication: Into the square: on the complexity of some quadratic-time solvable problems