Maximum common induced subgraph parameterized by vertex cover

DOI10.1016/j.ipl.2013.11.007zbMath1284.68274OpenAlexW2011162901WikidataQ115926550 ScholiaQ115926550MaRDI QIDQ2445395

Faisal N. Abu-Khzam

Publication date: 14 April 2014

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2013.11.007

zbMATH Keywords

graph algorithmsvertex coverfixed-parameter tractabilitymaximum common subgraphcommon subgraph isomorphism

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Streaming deletion problems parameterized by vertex cover, On the complexity of various parameterizations of common induced subgraph isomorphism, Streaming deletion problems Parameterized by vertex cover, A fast discovery algorithm for large common connected induced subgraphs, Exploring the gap between treedepth and vertex cover through vertex integrity, Exploring the gap between treedepth and vertex cover through vertex integrity, Unnamed Item, Improved Hardness of Maximum Common Subgraph Problems on Labeled Graphs of Bounded Treewidth and Bounded Degree

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Charge and reduce: A fixed-parameter algorithm for string-to-string correction
• Improved upper bounds for vertex cover
• Finding the maximum common subgraph of a partial \(k\)-tree and a graph with a polynomially bounded number of spanning trees
• The parameterized complexity of the induced matching problem
• Graph isomorphism problem
• On the complexity of finding iso- and other morphisms for partial \(k\)- trees
• Enumerating all connected maximal common subgraphs in two graphs
• A note on the derivation of maximal common subgraphs of two directed or undirected graphs
• On Cutwidth Parameterized by Vertex Cover
• Graph Layout Problems Parameterized by Vertex Cover
• An Algorithm for Subgraph Isomorphism
• Matching graphs by pivoting
• Preprocessing Subgraph and Minor Problems: When Does a Small Vertex Cover Help?
• On the Complexity of the Maximum Common Subgraph Problem for Partial k-Trees of Bounded Degree
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Computing and Combinatorics