Parameterized complexity of streaming diameter and connectivity problems
From MaRDI portal
Cites work
- scientific article; zbMATH DE number 3869067 (Why is no real title available?)
- scientific article; zbMATH DE number 1424324 (Why is no real title available?)
- scientific article; zbMATH DE number 7053293 (Why is no real title available?)
- A story of diameter, radius, and (almost) Helly property
- Almost optimal super-constant-pass streaming lower bounds for reachability
- Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
- Better bounds for matchings in the streaming model
- Beyond Helly graphs: the diameter problem on absolute retracts
- Computing graph distances parameterized by treewidth and diameter
- Depth First Search in the Semi-streaming Model
- Depth-first search is inherently sequential
- Diameter computation on H-minor free graphs and graphs of bounded (distance) VC-dimension
- Diameter determination on restricted graph families
- Distributed exact shortest paths in sublinear time
- Dynamic graph stream algorithms in \(o(n)\) space
- Fast approximation algorithms for the diameter and radius of sparse graphs
- Fast diameter computation within split graphs
- Fixed parameter tractability of graph deletion problems over data streams
- Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
- Graph Distances in the Data-Stream Model
- Graph streaming lower bounds for parameter estimation and property testing via a streaming XOR lemma
- Graph theory with applications
- Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams
- Multi-pass graph streaming lower bounds for cycle counting, MAX-CUT, matching size, and other problems
- Multivariate analysis of orthogonal range searching and graph distances
- Near-quadratic lower bounds for two-pass graph streaming algorithms
- Nondeterminism within $P^ * $
- On graph problems in a semi-streaming model
- Parameterized Streaming: Maximal Matching and Vertex Cover
- Parameterized complexity of diameter
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Streaming deletion problems parameterized by vertex cover
- Streaming kernelization
- Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs
- Superlinear lower bounds for multipass graph processing
- The streaming complexity of cycle counting, sorting by reversals, and other problems
- Tight bounds for graph problems in insertion streams
- Towards a theory of parameterized streaming algorithms
- Vertex cover: Further observations and further improvements
- Vertex packings: Structural properties and algorithms
- Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) time
This page was built for publication: Parameterized complexity of streaming diameter and connectivity problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6968988)
