Embedding and canonizing graphs of bounded genus in logspace

DOI10.1145/2591796.2591865MaRDI QIDQ5259572zbMATH OpenOpenAlexFDO

Authors Michael Elberfeld, Ken-ichi Kawarabayashi

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

zbMATH Keywords

computational complexitygraph embeddingisomorphismlogspaceEuler genusalgorithmic graph theory

Mathematics Subject Classification ID

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)

Recommendations

• Planarity testing revisited
• Canonizing Graphs of Bounded Tree Width in Logspace
• Canonizing graphs of bounded tree width in logspace
• scientific article; zbMATH DE number 4001498
• Space complexity of perfect matching in bounded genus bipartite graphs

Cites work

• scientific article; zbMATH DE number 5485440 (Why is no real title available?)
• scientific article; zbMATH DE number 5485574 (Why is no real title available?)
• Advances in Cryptology – CRYPTO 2004
• Answering \(n^{2+o(1)}\) counting queries with differential privacy is hard
• Bounds on the sample complexity for private learning and private data release
• Characterizing the sample complexity of private learners
• Collusion-secure fingerprinting for digital data
• Differential privacy and the fat-shattering dimension of linear queries
• Efficient algorithms for privately releasing marginals via convex relaxations
• Faster algorithms for privately releasing marginals
• Faster private release of marginals on small databases
• Interactive privacy via the median mechanism
• Iterative Constructions and Private Data Release
• Lower bounds in differential privacy
• New Efficient Attacks on Statistical Disclosure Control Mechanisms
• On the complexity of differentially private data release, efficient algorithms and hardness results
• On the geometry of differential privacy
• Our Data, Ourselves: Privacy Via Distributed Noise Generation
• Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
• The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
• Theory of Cryptography

Cited in

(12)

• Approximation in (poly-) logarithmic space
• Evaluating monotone circuits on surfaces
• Frameworks for designing in-place graph algorithms
• A framework for 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
• On the parameterized parallel complexity and the vertex cover problem
• Logspace Reduction of Directed Reachability for Bounded Genus Graphs to the Planar Case

Describes a project that uses

Uses Software

• SuLQ

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)