Polynomial-Time Algorithms for Subgraph Isomorphism in Small Graph Classes of Perfect Graphs

DOI10.1007/978-3-319-06089-7_15zbMath1406.05104OpenAlexW2169699292MaRDI QIDQ5410645

Yota Otachi, Ryuhei Uehara, Matsuo Konagaya

Publication date: 16 April 2014

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-06089-7_15

zbMATH Keywords

NP-completenesspolynomial-time algorithmsubgraph isomorphismgraph class

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Perfect graphs (05C17) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

This page was built for publication: Polynomial-Time Algorithms for Subgraph Isomorphism in Small Graph Classes of Perfect Graphs