Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity
From MaRDI portal
Publication:2134740
DOI10.1007/S00453-021-00918-4OpenAlexW4206084211MaRDI QIDQ2134740
Valia Mitsou, Hervé Hocquard, Théo Pierron, Dimitri Lajou, Florent Foucaud
Publication date: 3 May 2022
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1910.01099
Cites Work
- Fundamentals of parameterized complexity
- List H-coloring a graph by removing few vertices
- Separator-based data reduction for signed graph balancing
- Complexity of planar signed graph homomorphisms to cycles
- Parameterized coloring problems on chordal graphs
- Strong computational lower bounds via parameterized complexity
- On the parameterized complexity of multiple-interval graph problems
- Almost 2-SAT is fixed-parameter tractable
- On the complexity of H-coloring
- The node-deletion problem for hereditary properties is NP-complete
- Signed graphs
- The complexity of colouring symmetric relational systems
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Which problems have strongly exponential complexity?
- Negative (and positive) circles in signed graphs: a problem collection
- A complexity dichotomy for signed \(\mathbf{H}\)-colouring
- On the complexity of \(\mathbb{H}\)-coloring for special oriented trees
- Parameterized complexity of vertex colouring
- Parameterized complexity of finding subgraphs with hereditary properties.
- On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
- Subexponential algorithms for variants of the homomorphism problem in string graphs
- The complexity of signed graph and edge-coloured graph homomorphisms
- The recognition of bound quivers using edge-coloured homomorphisms
- On the notion of balance of a signed graph
- The Approximability of Constraint Satisfaction Problems
- Vertex Coloring of Comparability+ke and –ke Graphs
- Edge-Deletion Problems
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- A Proof of the CSP Dichotomy Conjecture
- Homomorphisms of Signed Graphs
- Fine-Grained Parameterized Complexity Analysis of Graph Coloring Problems
- The Complexity of Homomorphisms of Signed Graphs and Signed Constraint Satisfaction
- Constraint Satisfaction Parameterized by Solution Size
- Parameterized Algorithms
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity
