Compatible topologies on graphs: an application to graph isomorphism problem complexity

DOI10.1016/J.TCS.2006.07.010MaRDI QIDQ2508982zbMATH OpenOpenAlexFDO

Authors Alain Bretto, Alain Faisant, Thierry Vallée

Publication date 20 October 2006

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2006.07.010

zbMATH Keywords

compatible topology on graphcomplexity theorygraph isomorphism problemhomeomorphism problempolynomial-time equivalence

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Generalities in topology (54A99) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computing methodologies for image processing (68U10)

Recommendations

• scientific article; zbMATH DE number 4011932
• HOMEOMORPHISM OF 2-COMPLEXES IS EQUIVALENT TO GRAPH ISOMORPHISM
• Compatible connectedness in graphs and topological spaces
• Z-graphic topology on undirected graph
• Graphs and topologies on discrete sets

Cites work

• A Jordan surface theorem for three-dimensional digital spaces
• A Topological Approach to Digital Topology
• Comparability Graphs and Digital Topology
• Graph isomorphism, general remarks
• scientific article; zbMATH DE number 3522018 (Why is no real title available?)
• scientific article; zbMATH DE number 3629845 (Why is no real title available?)
• scientific article; zbMATH DE number 477971 (Why is no real title available?)
• scientific article; zbMATH DE number 732167 (Why is no real title available?)
• scientific article; zbMATH DE number 2061146 (Why is no real title available?)
• Topological digital topology.

Cited in

(7)

• Testing homotopy equivalence is isomorphism complete
• Compact compatible topologies for posets and graphs
• scientific article; zbMATH DE number 4011932 (Why is no real title available?)
• Homotopy equivalence which is suitable for studying Khalimsky nD spaces
• HOMEOMORPHISM OF 2-COMPLEXES IS EQUIVALENT TO GRAPH ISOMORPHISM
• scientific article; zbMATH DE number 5054075 (Why is no real title available?)
• The SVE method for regular graph isomorphism identification

This page was built for publication: Compatible topologies on graphs: an application to graph isomorphism problem complexity

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