New graph decompositions with applications to emulations

In this paper we present a new type of graph decomposition calleda cut-cover that combines the notions of graph separators andt-neighborhood covers. We show that graphs with good cut-covers can be emulated in hypercubes and we show that planar and certain minor-excluded graphs have good cut-covers....

Full description

Saved in:
Bibliographic Details
Published in:Theory of computing systems 1997-02, Vol.30 (1), p.39-49
Main Authors: Kaklamanis, C., Krizanc, D., Rao, S.
Format: Article
Language:English
Subjects:
Computation
Decomposition
Graphs
Hypercubes
Networks
Separators
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper we present a new type of graph decomposition calleda cut-cover that combines the notions of graph separators andt-neighborhood covers. We show that graphs with good cut-covers can be emulated in hypercubes and we show that planar and certain minor-excluded graphs have good cut-covers. In particular, we show how to emulate anyN-node bounded degree planar graph or anyN-node bounded degree graph that excludes $$K_{log0(1)} N} $$ as a minor with constant slowdown on hypercube networks.
ISSN:1432-4350
1433-0490
DOI:10.1007/BF02679452