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

Hans L. Bodlaender; Ton Kloks; Rolf Niedermeier

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

Hans L. Bodlaender^*, Ton Kloks, Rolf Niedermeier

^*Corresponding author for this work

Research output: Contribution to journal › Article › Academic › peer-review

Abstract

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.

Original language	English
Pages (from-to)	1-8
Number of pages	8
Journal	Electronic Notes in Discrete Mathematics
Volume	3
Publication status	Published - 1 Dec 1999
Externally published	Yes

Cite this

@article{d389faf08fcf47a3b3579a55042375b4,

title = "SIMPLE MAX-CUT for unit interval graphs and graphs with few P4s",

abstract = "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.",

author = "Bodlaender, {Hans L.} and Ton Kloks and Rolf Niedermeier",

year = "1999",

month = dec,

day = "1",

language = "English",

volume = "3",

pages = "1--8",

journal = "Electronic Notes in Discrete Mathematics",

issn = "1571-0653",

publisher = "Elsevier",

}

TY - JOUR

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

AU - Bodlaender, Hans L.

AU - Kloks, Ton

AU - Niedermeier, Rolf

PY - 1999/12/1

Y1 - 1999/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=53149090152&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:53149090152

SN - 1571-0653

VL - 3

SP - 1

EP - 8

JO - Electronic Notes in Discrete Mathematics

JF - Electronic Notes in Discrete Mathematics

ER -

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

Abstract

Other files and links

Fingerprint

Cite this