๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Parallel algorithms for fractional and maximal independent sets in planar graphs

โœ Scribed by N. Dadoun; D.G. Kirkpatrick

Publisher
Elsevier Science
Year
1990
Tongue
English
Weight
947 KB
Volume
27
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

Maximal independent sets in bipartite gr
Maximal independent sets in bipartite graphs
โœ Jiuqiang Liu ๐Ÿ“‚ Article ๐Ÿ“… 1993 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 458 KB ๐Ÿ‘ 1 views

## Abstract A maximal independent set of a graph __G__ is an independent set that is not contained properly in any other independent set of __G.__ In this paper, we determine the maximum number of maximal independent sets among all bipartite graphs of order __n__ and the extremal graphs as well as

Approximation Algorithms for Independent
Approximation Algorithms for Independent Sets in Map Graphs
โœ Zhi-Zhong Chen ๐Ÿ“‚ Article ๐Ÿ“… 2001 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 172 KB

This paper presents polynomial-time approximation algorithms for the problem of computing a maximum independent set in a given map graph G with or without weights on its vertices. If G is given together with a map, then a ratio of 1 + ฮด can be achieved by a quadratic-time algorithm for any given con

Efficient Sequential and Parallel Algori
Efficient Sequential and Parallel Algorithms for Maximal Bipartite Sets
โœ D. Pearson; V.V. Vazirani ๐Ÿ“‚ Article ๐Ÿ“… 1993 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 344 KB

A maximal bipartite set (MBS) in an undirected graph \(G=(V, E)\) is a maximal collection of vertices \(B \subseteq V\) whose induced subgraph is bipartite. In this paper we present efficient sequential (linear time) and parallel (NC) algorithms for constructing an MBS. 1.1993 Acatemic Press, Inc