Paper Info
Title
Asynchronous P Systems for the Maximum Independent Set and Related Graph Problems
Abstract
In the present paper, we consider fully asynchronous parallelism in membrane computing, and propose asynchronous P systems for three graph problems, which are the maximum independent set, the minimum vertex cover, and the maximum clique. We first propose an asynchronous P system that solves the maximum independent set for a graph with n nodes, and show that the proposed P system works in O(n2 · 2n) sequential steps or O(n2) parallel steps using O(n2) kinds of objects. We next propose an asynchronous P system that solves the minimum vertex cover and the maximum clique for a graph with n nodes by reduction to the maximum independent set, and show that the proposed P system works in O(n2 · 2n) sequential steps or O(n2) parallel steps using O(n2) kinds of objects.
Year
DOI
Venue
2013
10.1109/IPDPSW.2013.16
Parallel and Distributed Processing Symposium Workshops & PhD Forum
Keywords
Field
DocType
maximum independent set,n node,related graph problems,minimum vertex,asynchronous p systems,asynchronous p system,proposed p system work,graph problem,parallel step,maximum clique,asynchronous parallelism,sequential step,clique,skin,independent set,computational modeling,tin,graph theory,vertex cover,computational complexity,membrane computing,set theory,minimum vertex cover,parallel processing
Perfect graph,Discrete mathematics,Clique graph,Vertex (graph theory),Edge cover,Theoretical computer science,Independent set,Feedback vertex set,Mathematics,Split graph,Maximal independent set
Conference
ISBN
Citations 
PageRank 
978-0-7695-4979-8
0
0.34
References 
Authors
8
2
Name
Order
Citations
PageRank
Kohei Tanaka1616.70
Akihiro Fujiwara212227.25