Affordable Access

Publisher Website

The subgraph homeomorphism problem for small wheels

Authors
Journal
Discrete Mathematics
0012-365X
Publisher
Elsevier
Publication Date
Volume
71
Issue
2
Identifiers
DOI: 10.1016/0012-365x(88)90066-0
Disciplines
  • Computer Science

Abstract

Abstract The subgraph homeomorphism problem, where the pattern graph is a wheel with four or five spokes, is studied. The most important result is that any 3-connected graph satisfying a simple edge connectivity condition has a W 5-homeomorph iff it has a vertex ∨ of degree at least 5 and a circuit, disjoint from ∨, of length at least 5. Efficient algorithms are described for these cases of the subgraph homeomorphism problem.

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments

More articles like this

The directed subgraph homeomorphism problem

on Theoretical Computer Science Jan 01, 1980

The subgraph homeomorphism problem

on Journal of Computer and System... Jan 01, 1980

An approach to the subgraph homeomorphism problem

on Theoretical Computer Science Jan 01, 1985

O(n2.5) time algorithms for the subgraph homeomorp...

on Journal of Algorithms Jan 01, 1987
More articles like this..