Skip navigation
Skip navigation

Graph Isomorphism for Graph Classes Characterized by Two Forbidden Induced Subgraphs

Kratsch, Stefan; Schweitzer, Pascal

Description

We study the complexity of the Graph Isomorphism problem on graph classes that are characterized by a finite number of forbidden induced subgraphs, focusing mostly on the case of two forbidden subgraphs. We show hardness results and develop techniques for the structural analysis of such graph classes, which applied to the case of two forbidden subgraphs give the following results: A dichotomy into isomorphism complete and polynomial-time solvable graph classes for all but finitely many cases,...[Show more]

CollectionsANU Research Publications
Date published: 2012
Type: Conference paper
URI: http://hdl.handle.net/1885/68879
Source: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
DOI: 10.1007/978-3-642-34611-8_7

Download

File Description SizeFormat Image
01_Kratsch_Graph_Isomorphism_for_Graph_2012.pdf220.6 kBAdobe PDF    Request a copy


Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  23 August 2018/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator