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

DOI10.1016/J.TCS.2006.07.010zbMATH Open1101.68065OpenAlexW2018560356MaRDI QIDQ2508982FDOQ2508982

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Jordan surface theorem for three-dimensional digital spaces
• A Topological Approach to Digital Topology
• Graph isomorphism, general remarks
• Topological digital topology.
• Comparability Graphs and Digital Topology
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (7)

• Title not available (Why is that?)
• Compact compatible topologies for posets and graphs
• HOMEOMORPHISM OF 2-COMPLEXES IS EQUIVALENT TO GRAPH ISOMORPHISM
• The SVE method for regular graph isomorphism identification
• Title not available (Why is that?)
• Homotopy equivalence which is suitable for studying Khalimsky \(n\)D 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)