Monash University
Browse
tr-2012-270-full.pdf (825.19 kB)

Graphs with no 7-wheel subdivision,version II

Download (825.19 kB)
report
posted on 2022-07-25, 00:17 authored by R Robinson, G Farr
The subgraph homeomorphism problem, SHP(H), has been shown to be polynomial-time solvable for any fixed pattern graph H, but practical algorithms have been developed only for a few specific pattern graphs. Among these are the wheels with four, five, and six spokes. This paper examines the subgraph homeomorphism problem where the pattern graph is a wheel with seven spokes, and gives a result that describes graphs with no W7-subdivision, showing how they can be built up, using certain operations, from ‘pieces’ of at most 37 vertices. The result leads to an efficient algorithm solving SHP(W7). This algorithm has features that are similar to those in some parameterized algorithms, and may provide useful insight in searching for a fixed-parameter tractable result for SHP(Wk), with parameter k. This technical report is an updated version of Technical Report 2009/239 [10].

History

Technical report number

2012/270

Year of publication

2012

Usage metrics

    Monash Information Technology Technical Reports

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC