scientific article; zbMATH DE number 139780

MaRDI QIDQ4028103zbMATH OpenFDO

Authors Peter Damaschke

Publication date 28 March 1993

zbMATH Keywords

NP-completecographssubgraph isomorphism

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Cited in

(13)

• On retracts, absolute retracts, and foldings in cographs
• Critical properties of bipartite permutation graphs
• When can graph hyperbolicity be computed in linear time?
• Finding a chain graph in a bipartite permutation graph
• Edge contractions in subclasses of chordal graphs
• Subgraph isomorphism in graph classes
• Containment relations in split graphs
• Polynomial-time algorithms for subgraph isomorphism in small graph classes of perfect graphs
• Characterizations of cographs as intersection graphs of paths on a grid
• Induced subgraph isomorphism on proper interval and bipartite permutation graphs
• Parameterized complexity of induced graph matching on claw-free graphs
• Subgraph isomorphism on graph classes that exclude a substructure
• Edge contractions in subclasses of chordal graphs

This page was built for publication:

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