Exact algorithms for the vertex separator problem in graphs

DOI10.1002/NET.20420zbMATH Open1219.05192OpenAlexW2139900483MaRDI QIDQ3008917FDOQ3008917

Authors: Victor F. Cavalcante, Cid Carvalho de Souza 

Publication date: 22 June 2011

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.20420

Recommendations

• An exact algorithm for solving the vertex separator problem
• The vertex separator problem: algorithms and computations
• An exact algorithm for graph partitioning
• The vertex separator problem: a polyhedral investigation
• Exact algorithms for difficult graph problems
• An exact combinatorial algorithm for minimum graph bisection
• scientific article; zbMATH DE number 4062622
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• Theoretical Computer Science
• scientific article; zbMATH DE number 1953093

zbMATH Keywords

integer programmingcutting planesLagrangian relaxationrelax-and-cutvertex separator problem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Lower and upper bounds for the degree-constrained minimum spanning tree problem
• The vertex separator problem: a polyhedral investigation
• Decomposing Matrices into Blocks
• The vertex separator problem: algorithms and computations
• Set covering algorithms using cutting planes, heuristics, and subgradient optimization: A computational study
• Title not available (Why is that?)
• Non delayed relax-and-cut algorithms
• A restricted Lagrangean approach to the traveling salesman problem
• Optimal rectangular partitions
• Stronger \(K\)-tree relaxations for the vehicle routing problem
• Algorithms – ESA 2005
• A relax-and-cut algorithm for the set partitioning problem
• An enhanced TSP-based heuristic for makespan minimization in a flow shop with setup times
• Lagrangian Relaxation and Cutting Planes for the Vertex Separator Problem

Cited In (9)

• An exact combinatorial algorithm for minimum graph bisection
• A hybrid breakout local search and reinforcement learning approach to the vertex separator problem
• Finding minimum balanced separators -- an exact approach
• Title not available (Why is that?)
• Lagrangian Relaxation and Cutting Planes for the Vertex Separator Problem
• The vertex separator problem: algorithms and computations
• A quality and distance guided hybrid algorithm for the vertex separator problem
• An I/O-Efficient Algorithm for Computing Vertex Separators on Multi-Dimensional Grid Graphs and Its Applications
• Vertex Exponential Algorithms for Connected f-Factors

This page was built for publication: Exact algorithms for the vertex separator problem in graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3008917)