Embedding and canonizing graphs of bounded genus in logspace
DOI10.1145/2591796.2591865zbMATH Open1315.68254OpenAlexW1985953373MaRDI QIDQ5259572FDOQ5259572
Ken-ichi Kawarabayashi, Michael Elberfeld
Publication date: 26 June 2015
Published in: Proceedings of the forty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2591796.2591865
Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph designs and isomorphic decomposition (05C51)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Theory of Cryptography
- The geometry of differential privacy: the small database and approximate cases
- On the geometry of differential privacy
- Interactive privacy via the median mechanism
- The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
- Lower Bounds in Differential Privacy
- Iterative Constructions and Private Data Release
- Differential Privacy and the Fat-Shattering Dimension of Linear Queries
- Our Data, Ourselves: Privacy Via Distributed Noise Generation
- On the complexity of differentially private data release
- Collusion-secure fingerprinting for digital data
- Advances in Cryptology – CRYPTO 2004
- New Efficient Attacks on Statistical Disclosure Control Mechanisms
- Bounds on the Sample Complexity for Private Learning and Private Data Release
- Answering n {2+o(1)} counting queries with differential privacy is hard
- Characterizing the sample complexity of private learners
- Faster Algorithms for Privately Releasing Marginals
- Faster private release of marginals on small databases
- Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
- Privately releasing conjunctions and the statistical query barrier
- Efficient algorithms for privately releasing marginals via convex relaxations
Cited In (11)
- Approximation in (Poly-) logarithmic space
- On the Parameterized Parallel Complexity and the Vertex Cover Problem
- Frameworks for designing in-place graph algorithms
- Depth-First Search Using $$O(n)$$ Bits
- Sublinear-space approximation algorithms for Max \(r\)-SAT
- Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits
- Space efficient algorithm for solving reachability using tree decomposition and separators
- Approximation in (Poly-) Logarithmic Space
- Space-efficient algorithms for reachability in directed geometric graphs
- Logspace Reduction of Directed Reachability for Bounded Genus Graphs to the Planar Case
- A Framework for In-place Graph Algorithms
Uses Software
This page was built for publication: Embedding and canonizing graphs of bounded genus in logspace
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5259572)
