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

DOI10.1007/3-540-60922-9_37MaRDI QIDQ4593952zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

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

Cited in

(11)

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

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)