A linear algorithm for resource four-partitioning four-connected planar graphs

Given a connected graph G = (V,E), a set V r ⊆ V of r special vertices, four distinct base vertices u 1 , u 2 , u 3 , u 4 ∈ V and four natural numbers r 1 , r 2 , r 3 , r 4 such that Σ j=1 4 r j = r, we wish to find a partition V 1 , V 2 , V 3 , V 4 of V such that V i contains u i and r i vertices f...

Full description

Saved in:
Bibliographic Details
Main Authors: Awal, T, Rahman, M S
Format: Conference Proceeding
Language:English
Subjects:
4-canonical decomposition
4-connected graph
Algorithm
Algorithm design and analysis
Clocks
Computer science
Conferences
Face
Partitioning algorithms
Planar graph
Resource 4-partition
Resource bipartition
Servers
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Given a connected graph G = (V,E), a set V r ⊆ V of r special vertices, four distinct base vertices u 1 , u 2 , u 3 , u 4 ∈ V and four natural numbers r 1 , r 2 , r 3 , r 4 such that Σ j=1 4 r j = r, we wish to find a partition V 1 , V 2 , V 3 , V 4 of V such that V i contains u i and r i vertices from V r , and V i induces a connected subgraph of G for each i, 1 ≤ i ≤ 4. We call a vertex in V r a resource vertex and the problem above of partitioning vertices of G as the resource four-partitioning problem. In this paper, we give a linear algorithm for finding a resource four-partition of a four-connected planar graph G with base vertices located on the same face of a planar embedding. Our algorithm is based on a 4-canonical decomposition and st-numbering of G.
DOI:10.1109/ICELCE.2010.5700745