Approximation in (Poly-) Logarithmic Space
From MaRDI portal
Publication:5089177
Cites work
- A framework for in-place graph algorithms
- A general Sequential Time-Space Tradeoff for Finding Unique Elements
- A parallel approximation algorithm for positive linear programming
- A shortcut to (sun)flowers: kernels in logarithmic space or linear time
- A simple local 3-approximation algorithm for vertex cover
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
- A time-space tradeoff for sorting on non-oblivious machines
- Advice classes of parametrized tractability
- Algorithmic construction of sets for k -restrictions
- Analytical approach to parallel repetition
- Approximating linear programming is log-space complete for P
- Approximation Resistance from Pairwise-Independent Subgroups
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Embedding and canonizing graphs of bounded genus in logspace
- scientific article; zbMATH DE number 1383709 (Why is no real title available?)
- scientific article; zbMATH DE number 1453080 (Why is no real title available?)
- Inapproximability of vertex cover and independent set in bounded degree graphs
- Logspace optimization problems and their approximability properties
- Nondeterminism within $P^ * $
- Parallel approximation algorithms by positive linear programming
- Parameterized algorithms
- Parameterized complexity of directed Steiner tree on sparse graphs
- Polynomial kernels for \textsc{Dominating Set} in graphs of bounded degeneracy and beyond
- Relationships between nondeterministic and deterministic tape complexities
- Selection and sorting in the ``restore model
- Selection and sorting with limited storage
- Selection from read-only memory and sorting with minimum data movement
- Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
- Symmetric Complementation
- The complexity of planarity testing
- The probabilistic method. With an appendix on the life and work of Paul Erdős.
- Undirected connectivity in log-space
- Uniform-circuit and logarithmic-space approximations of refined combinatorial optimization problems
- Universal classes of hash functions
- Upper bounds for time-space trade-offs in sorting and selection
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
Cited in
(4)
This page was built for publication: Approximation in (Poly-) Logarithmic Space
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5089177)
