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

Maximum weight independent set of circular-arc graph and its application

โœ Scribed by Swagata Mandal; Madhumangal Pal

Publisher
Springer-Verlag
Year
2006
Tongue
English
Weight
221 KB
Volume
22
Category
Article
ISSN
1598-5865

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

Maximum independent sets of circular-arc
Maximum independent sets of circular-arc graphs: Simplified algorithm and proofs
โœ Zheng, S. Q. ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 421 KB ๐Ÿ‘ 2 views

We present a simple optimal algorithm for the problem of finding maximum independent sets of circular-arc graphs. Given an intersection model S of a circular-arc graph G , our algorithm computes a maximum independent set of G in O ( n ) space and O ( n ) or O(n log n ) time, depending on whether the

Maximum genus and maximum nonseparating
Maximum genus and maximum nonseparating independent set of a 3-regular graph
โœ Yuangqiu Huang; Yanpei Liu ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 440 KB

A set J C V is called a nonseparating independent set (nsis) of a connected graph G = (V, E), if J is an independent set of G, i.e., E A {uv [ Vu, v E J} = 0, and G -J is connected. We call z(G) = maxJ{lJ[ tJ is an nsis of G} the nsis number of G. Let G be a 3-regular connected graph; we prove that