scientific article; zbMATH DE number 7053319

zbMATH Open1423.05183MaRDI QIDQ5743440FDOQ5743440

Authors: Liam Roditty, Virginia Vassilevska Williams 

Publication date: 10 May 2019

Full work available at URL: https://dl.acm.org/citation.cfm?id=2095183

Title of this publication is not available (Why is that?)

Recommendations

• Constant girth approximation for directed graphs in subquadratic time
• Separating sublinear time computations by approximate diameter
• Separating Sublinear Time Computations by Approximate Diameter
• Sublinear-time algorithms for approximating graph parameters
• Sublinear time algorithms for metric space problems
• Sublinear graph approximation algorithms
• Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
• Sublinear-time Algorithms
• Sublinear time algorithms
• scientific article; zbMATH DE number 5057523

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Approximation algorithms (68W25) Paths and cycles (05C38)

Cites Work

• The Spatial Complexity of Oblivious k-Probe Hash Functions
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• Color-coding
• Cycle bases in graphs characterization, algorithms, complexity, and applications
• All-Pairs Almost Shortest Paths
• Approximating the girth
• Minimum Weight Cycles and Triangles: Equivalences and Algorithms
• Finding and counting given length cycles
• Matrix multiplication via arithmetic progressions
• Cycles of even length in graphs
• Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
• General context-free recognition in less than cubic time
• Finding a Minimum Circuit in a Graph
• Title not available (Why is that?)
• Regularity Lemmas and Combinatorial Algorithms
• Faster algorithms for finding lowest common ancestors in directed acyclic graphs
• Approximate distance oracles
• Subcubic equivalences between path, matrix, and triangle problems
• Approximation algorithms for cycle packing problems
• Finding Even Cycles Even Faster
• Efficient approximation algorithms for shortest cycles in undirected graphs
• Faster algorithms for all-pairs approximate shortest paths in undirected graphs

Cited In (9)

• A distributed enumeration algorithm and applications to all pairs shortest paths, diameter\dots
• Faster Approximation Algorithms for Computing Shortest Cycles on Weighted Graphs
• Title not available (Why is that?)
• Approximating cycles in directed graphs: fast algorithms for girth and roundtrip spanners
• On approximating the \(d\)-girth of a graph
• Minimum cuts and shortest cycles in directed planar graphs via noncrossing shortest paths
• Fast distributed algorithms for girth, cycles and small subgraphs
• Computing the depth distribution of a set of boxes
• Efficient enumeration of subgraphs and induced subgraphs with bounded girth

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5743440)