On the complexity of various parameterizations of common induced subgraph isomorphism
type: Item
instance of: scholarly article
title: On the complexity of various parameterizations of common induced subgraph isomorphism
title: On the Complexity of Various Parameterizations of Common Induced Subgraph Isomorphism
zbMATH Open document ID: 1378.68055
zbMATH Open document ID: 1396.68053
DOI: 10.1007/978-3-319-19315-1_1
DOI: 10.1016/J.TCS.2017.07.010
author: Faisal N. Abu-Khzam
author: Édouard Bonnet
author: Florian Sikora
published in: Theoretical Computer Science
published in: Lecture Notes in Computer Science
publication date: 2017-09-28T00:00:00Z
publication date: 2015-09-15T00:00:00Z
full work available at URL: https://arxiv.org/abs/1412.1261
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C60
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 6781971
zbMATH DE Number: 6482454
zbMATH Keywords: induced common isomorphism
zbMATH Keywords: parameterized complexity
zbMATH Keywords: kernelization
zbMATH Keywords: ETH-based lower bounds
MaRDI profile type: Publication
OpenAlex ID: W2971952735
OpenAlex ID: W1506667737
arXiv ID: 1412.1261
cites work: Maximum common induced subgraph parameterized by vertex cover
cites work: Kernelization Lower Bounds by Cross-Composition
cites work: The Turing way to parameterized complexity
cites work: Improved upper bounds for vertex cover
cites work: Fundamentals of parameterized complexity
cites work: Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
cites work: Fixed-parameter tractability, definability, and model-checking
cites work: Q4198056
cites work: The parameterized complexity of the induced matching problem
cites work: Q5710169
cites work: Finding the maximum common subgraph of a partial \(k\)-tree and a graph with a polynomially bounded number of spanning trees
cites work: Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
cites work: Algorithmic Aspects of Dominator Colorings in Graphs
cites work: Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems
cites work: Q4028103
cites work: Deciding First-Order Properties of Nowhere Dense Graphs
cites work: Induced subgraph isomorphism on proper interval and bipartite permutation graphs
cites work: Which problems have strongly exponential complexity?
cites work: Q5365080
cites work: Q5365079
cites work: Cleaning interval graphs
cites work: Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
description: scientific article; zbMATH DE number 6482454
alternative label: On the Complexity of Various Parameterizations of Common Induced Subgraph Isomorphism