NP-completeness of the Planar Separator Problems

DOI10.7155/JGAA.00130zbMath1178.68378OpenAlexW2115030814MaRDI QIDQ5301395

Junichiro Fukuyama

Publication date: 19 January 2009

Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/45389

zbMATH Keywords

unweighted graphsEdge Separator ProblemPlanar Separator ProblemVertex Separator Problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (11)

Continuous quadratic programming formulations of optimization problems on graphs ⋮ A quality and distance guided hybrid algorithm for the vertex separator problem ⋮ The vertex \(k\)-cut problem ⋮ Casting Light on the Hidden Bilevel Combinatorial Structure of the Capacitated Vertex Separator Problem ⋮ On integer and bilevel formulations for the \(k\)-vertex cut problem ⋮ An exact algorithm for solving the vertex separator problem ⋮ Computation in Causal Graphs ⋮ Knowledge Discovery in Graphs Through Vertex Separation ⋮ A multilevel bilinear programming algorithm for the vertex separator problem ⋮ The critical node detection problem in networks: a survey ⋮ Balanced line separators of unit disk graphs

This page was built for publication: NP-completeness of the Planar Separator Problems