An exact algorithm for subgraph homeomorphism

DOI10.1016/j.jda.2008.10.003zbMath1209.05247OpenAlexW2036621153MaRDI QIDQ1044032

Martin Wahlen, Andrzej Lingas

Publication date: 10 December 2009

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2008.10.003

zbMATH Keywords

time complexityspace complexitydisjoint pathssubgraph homeomorphism

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• The complexity of subgraph isomorphism for classes of partial k-trees
• Inclusion and exclusion algorithm for the Hamiltonian path problem
• Dynamic programming meets the principle of inclusion and exclusion
• On the complexity of finding iso- and other morphisms for partial \(k\)- trees
• Embeddings of \(k\)-connected graphs of pathwidth \(k\)
• Graph minors. XIII: The disjoint paths problem
• Fast multiplication of large numbers
• A Dynamic Programming Approach to Sequencing Problems
• Fourier meets M\"{o}bius: fast subset convolution
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: An exact algorithm for subgraph homeomorphism