The vertex separator problem: algorithms and computations

DOI10.1007/s10107-005-0573-8zbMath1099.90069OpenAlexW1964488715MaRDI QIDQ2487851

Egon Balas, Cid Carvalho De Souza

Publication date: 8 August 2005

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-005-0573-8

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Related Items

The multi-terminal vertex separator problem: branch-and-cut-and-price, Component-cardinality-constrained critical node problem in graphs, Continuous quadratic programming formulations of optimization problems on graphs, MIP reformulations of the probabilistic set covering problem, A quality and distance guided hybrid algorithm for the vertex separator problem, A branch-and-price algorithm for capacitated hypergraph vertex separation, General variable neighborhood search for computing graph separators, 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, The multi-terminal vertex separator problem: polyhedral analysis and branch-and-cut, Knowledge Discovery in Graphs Through Vertex Separation, Exact algorithms for the vertex separator problem in graphs, The MIN-cut and vertex separator problem, The critical node detection problem in networks: a survey, A hybrid breakout local search and reinforcement learning approach to the vertex separator problem, Optimizing over the split closure, The vertex separator problem: a polyhedral investigation

Uses Software

• MatrixMarket
• XPRESS

Cites Work

• The vertex separator problem: a polyhedral investigation
• A Separator Theorem for Planar Graphs
• Nested Dissection of a Regular Finite Element Mesh