Computing list homomorphisms in geometric intersection graphs
From MaRDI portal
Publication:6039432
DOI10.1007/978-3-031-15914-5_23arXiv2202.08896MaRDI QIDQ6039432
Paweł Rzążewski, Sándor Kisfaludi-Bak, Karolina Okrasa
Publication date: 5 May 2023
Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2202.08896
graph homomorphismsexponential time hypothesisgeometric intersection graphssubexponential-time algorithms
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of colouring problems on dense graphs
- String graphs. II: Recognizing string graphs is NP-hard
- String graphs. I: The number of critical nonstring graphs is infinite
- Unit disk graphs
- Intersection graphs of segments
- Which problems have strongly exponential complexity?
- Algorithmic graph theory and perfect graphs
- Subexponential algorithms for variants of the homomorphism problem in string graphs
- Finding, hitting and packing cycles in subexponential time on unit disk graphs
- Graph Theory for Systems Biology
- Representation of a finite graph by a set of intervals on the real line
- A Framework for Exponential-Time-Hypothesis--Tight Algorithms and Lower Bounds in Geometric Intersection Graphs
- Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams
- Max-tolerance graphs as intersection graphs
- Separators for sphere-packings and nearest neighbor graphs
- Geometric separation and exact solutions for the parameterized independent set problem on disk graphs
- EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs
- On the Exact Complexity of Hamiltonian Cycle and q-Colouring in Disk Graphs
- Algorithms – ESA 2005
- Approximation and Online Algorithms
- Optimality program in segment and string graphs
- On the complexity of \(k\)-SAT
This page was built for publication: Computing list homomorphisms in geometric intersection graphs
