scientific article; zbMATH DE number 1414279
From MaRDI portal
Publication:4942616
zbMath0941.05515MaRDI QIDQ4942616
Hans L. Bodlaender, Klaus Jansen
Publication date: 16 March 2000
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
chordal graphscographsNP-completesplit graphspolynomial timemax-cut problemtripartite graphundirected path graphscomplement of a bipartite graph
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (10)
Unnamed Item ⋮ Complexity-separating graph classes for vertex, edge and total colouring ⋮ MaxCut on permutation graphs is NP‐complete ⋮ Algorithmic aspects of switch cographs ⋮ \textsc{max-cut} and containment relations in graphs ⋮ Solving a cut problem in bipartite graphs by linear programming: application to a forest management problem ⋮ max-cut and Containment Relations in Graphs ⋮ Revising Johnson's table for the 21st century ⋮ Maximum cut on line and total graphs ⋮ Vertex Deletion Problems on Chordal Graphs
This page was built for publication:
