The complexity of recognizing geometric hypergraphs
From MaRDI portal
Cites work
- -nets and simplex range queries
- \(\exists\mathbb{R}\)-complete decision problems about symmetric Nash equilibria in symmetric multi-player games
- A Catalog of EXISTS-R-Complete Decision Problems About Nash Equilibria in Multi-Player Games.
- Algorithmic solvability of the lifting-extension problem
- Completeness for the complexity class \(\forall \exists \mathbb{R}\) and area-universality
- Complexity of geometric \(k\)-planarity for fixed \(k\)
- Complexity of some geometric and topological problems
- Computing all maps into a sphere
- Covering polygons is even Harder
- Density of range capturing hypergraphs
- Embeddability in R^3 is NP-hard
- Embeddability in the 3-sphere is decidable
- Extremal problems for geometric hypergraphs
- Fixed points, Nash equilibria, and the existential theory of the reals
- Framework for ER-completeness of two-dimensional packing problems
- Geometric embeddability of complexes is \(\exists\mathbb{R}\)-complete
- Hardness of embedding simplicial complexes in R^d
- scientific article; zbMATH DE number 4092241 (Why is no real title available?)
- scientific article; zbMATH DE number 17663 (Why is no real title available?)
- scientific article; zbMATH DE number 1520171 (Why is no real title available?)
- Integer realizations of disk and segment graphs
- Intersection graphs of rays and grounded segments
- Intersection graphs of segments
- Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
- On classifying continuous constraint satisfaction problems
- On restricted nonnegative matrix factorization
- On some properties of convex curves and surfaces.
- On some theorems regarding ellipsoid.
- On The Chromatic Number of Geometric Hypergraphs
- On the computational complexity of decision problems about multi-player Nash equilibria
- Optimal greedy algorithms for indifference graphs
- Polynomial-time computation of homotopy groups and Postnikov systems in fixed dimension
- Realizability of graphs and linkages
- Realization spaces of 4-polytopes are universal
- Recognition of Circle Graphs
- Recognition of unit segment and polyline graphs is \(\exists \mathbb{R} \)-complete
- Recognizing string graphs in NP
- Representing graphs and hypergraphs by touching polygons in 3D
- Small-size -nets for axis-parallel rectangles and boxes
- Smoothing the gap between NP and ER
- Sphere and dot product representations of graphs
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- The art gallery problem is \(\exists \mathbb{R}\)-complete
- The complexity of drawing a graph in a polygonal region
- The complexity of positive semidefinite matrix factorization
- The complexity of recognizing geometric hypergraphs
- The complexity of tensor rank
- The complexity of the Hausdorff distance
- The Roberts characterization of proper and unit interval graphs
- Tight lower bounds for the size of epsilon-nets
- Unit and single point interval graphs
This page was built for publication: The complexity of recognizing geometric hypergraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6988916)
