✦ LIBER ✦

SIMPLE MAX-CUT for unit interval graphs and graphs with few P4s

✍ Scribed by Hans L. Bodlaender; Ton Kloks; Rolf Niedermeier

Publisher: Elsevier Science
Year: 1999
Tongue: English
Weight: 56 KB
Volume: 3
Category: Article
ISSN: 1571-0653
DOI: 10.1016/s1571-0653(05)80014-9

No coin nor oath required. For personal study only.

✦ Synopsis

The SIMPLE MAX-CUT problem can be solved in linear time for unit interval graphs. We show also that for each constant q, the SIMPLE MAX-CUT problem can be solved in polynomial time for (q, q -4)-graphs.