✦ LIBER ✦

Sequential and parallel algorithms for the maximum-weight independent set problem on permutation graphs

✍ Scribed by Ming-Shing Yu; Lin Yu Tseng; Shoe-Jane Chang

Publisher: Elsevier Science
Year: 1993
Tongue: English
Weight: 428 KB
Volume: 46
Category: Article
ISSN: 0020-0190
DOI: 10.1016/0020-0190(93)90188-f

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

The maximum independent set problem for

The maximum independent set problem for cubic planar graphs

✍ James E. Burns 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 286 KB

An approximation algorithm for the maxim

An approximation algorithm for the maximum independent set problem in cubic planar graphs

✍ Elarbi Choukhmane; John Franco 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 289 KB 👁 1 views

A branch-and-price approach for the maxi

A branch-and-price approach for the maximum weight independent set problem

✍ Deepak Warrier; Wilbert E. Wilhelm; Jeffrey S. Warren; Illya V. Hicks 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 124 KB

Polynomial algorithms for the weighted p

Polynomial algorithms for the weighted perfect domination problems on chordal graphs and split graphs

✍ Maw-Shang Chang; Yi-Chang Liu 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 475 KB

On the nonseparating independent set pro

On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three

✍ Shuichi Ueno; Yoji Kajitani; Shin'ya Gotoh 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 350 KB

This paper shows that both the nonseparating independent set problem and feedback set problem can be solved in polynomial time for graphs with no vertex degree exceeding 3 by reducing the problems to the matroid parity problem.