Characterizing the complexity of subgraph isomorphism for graphs of bounded path-width

DOI10.1007/3-540-60922-9_37zbMATH Open1379.68164OpenAlexW1544045550MaRDI QIDQ4593952FDOQ4593952

Authors: Arvind Kumar Gupta, N. Nishimura 

Publication date: 16 November 2017

Published in: STACS 96 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-60922-9_37

Recommendations

• The complexity of subgraph isomorphism for classes of partial k-trees
• Everything you always wanted to know about the parameterized complexity of subgraph isomorphism (but were afraid to ask)
• Embeddings of \(k\)-connected graphs of pathwidth \(k\)
• Faster algorithms for subgraph isomorphism of \(k\)-connected partial \(k\)-trees
• Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Cited In (10)

• An algorithm using length-r paths to approximate subgraph isomorphism
• Tight Bounds for Graph Homomorphism and Subgraph Isomorphism
• Dichotomies for tree minor containment with structural parameters
• Embeddings of \(k\)-connected graphs of pathwidth \(k\)
• Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth
• Everything you always wanted to know about the parameterized complexity of subgraph isomorphism (but were afraid to ask)
• Maximum packing for \(k\)-connected partial \(k\)-trees in polynomial time
• Dichotomies for tree minor containment with structural parameters
• Title not available (Why is that?)
• Maximum packing for biconnected outerplanar graphs

This page was built for publication: Characterizing the complexity of subgraph isomorphism for graphs of bounded path-width

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4593952)