Subexponential algorithms for variants of the homomorphism problem in string graphs
From MaRDI portal
Publication:2301363
DOI10.1016/j.jcss.2019.12.004zbMath1435.68243arXiv1809.09345WikidataQ126434548 ScholiaQ126434548MaRDI QIDQ2301363
Karolina Okrasa, Paweł Rzążewski
Publication date: 24 February 2020
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1809.09345
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
05C85: Graph algorithms (graph-theoretic aspects)
05C62: Graph representations (geometric and intersection representations, etc.)
05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
Related Items
Finding Large $H$-Colorable Subgraphs in Hereditary Graph Classes, Unnamed Item, Unnamed Item, On cycle transversals and their connected variants in the absence of a small linear forest, Unnamed Item, An algorithmic framework for locally constrained homomorphisms, Computing list homomorphisms in geometric intersection graphs, Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity, List covering of regular multigraphs, Degeneracy of \(P_t\)-free and \(C_{\geq t}\)-free graphs with no large complete bipartite subgraphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On strongly planar not-all-equal 3SAT
- Fixed points, Nash equilibria, and the existential theory of the reals
- \(k-L(2,1)\)-labelling for planar graphs is NP-complete for \(k\geq 4\)
- Exact algorithms for \(L(2,1)\)-labeling of graphs
- The complexity of locally injective homomorphisms
- A complete complexity classification of the role assignment problem
- Cantor--Bernstein type theorem for locally constrained graph homomorphisms
- String graphs. II: Recognizing string graphs is NP-hard
- String graphs. I: The number of critical nonstring graphs is infinite
- String graphs requiring exponential representations
- Intersection graphs of segments
- Independent feedback vertex set for \(P_5\)-free graphs
- On the injective chromatic number of graphs
- Integer realizations of disk and segment graphs
- List homomorphisms and circular arc graphs
- On simplified NP-complete variants of \textsc{Monotone} 3\textsc{-Sat}
- Subexponential algorithms for variants of homomorphism problem in string graphs
- \(H\)-colouring \(P_t\)-free graphs in subexponential time
- Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree
- A dichotomy for minimum cost graph homomorphisms
- A Separator Theorem for String Graphs and its Applications
- Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams
- Locally Injective Graph Homomorphism: Lists Guarantee Dichotomy
- A Separator Theorem for Planar Graphs
- Labelling Graphs with a Condition at Distance 2
- Separators for sphere-packings and nearest neighbor graphs
- Coloring the square of a planar graph
- Geometric separation and exact solutions for the parameterized independent set problem on disk graphs
- Finding, Hitting and Packing Cycles in Subexponential Time on Unit Disk Graphs
- Every planar graph is the intersection graph of segments in the plane
- On the Exact Complexity of Hamiltonian Cycle and q-Colouring in Disk Graphs
- Near-Optimal Separators in String Graphs
- On Injective Colourings of Chordal Graphs
- Mathematical Foundations of Computer Science 2005
- Optimality program in segment and string graphs
- Recognizing string graphs in NP
- On the complexity of \(k\)-SAT
