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

complexity theorygraph isomorphism problemhomeomorphism problemcompatible topology on graphpolynomial-time equivalence

Mathematics Subject Classification ID

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

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

• 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?)
• A Jordan surface theorem for three-dimensional digital spaces
• A Topological Approach to Digital Topology
• Comparability Graphs and Digital Topology
• Graph isomorphism, general remarks
• Topological digital topology.

Cited in

(7)

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

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)