Branch and bound for the cutwidth minimization problem

DOI10.1016/j.cor.2012.05.016zbMath1349.90820OpenAlexW2160467939WikidataQ57856091 ScholiaQ57856091MaRDI QIDQ339558

Abraham Duarte, Rafael Martí, Eduardo G. Pardo, Juan José Pantrigo

Publication date: 11 November 2016

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2012.05.016

zbMATH Keywords

branch-and-bound algorithminteger programmingcutwidth

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Random graphs (graph-theoretic aspects) (05C80) Integer programming (90C10) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Related Items

Optimization procedures for the bipartite unconstrained 0-1 quadratic programming problem, Lower bounds for the bandwidth problem, Strong SDP based bounds on the cutwidth of a graph, Efficient iterated greedy for the two-dimensional bandwidth minimization problem, Multistart search for the cyclic cutwidth minimization problem, Tailored heuristics in adaptive large neighborhood search applied to the cutwidth minimization problem, A note on computational approaches for the antibandwidth problem

Uses Software

• GRASP
• CPLEX
• Tabu search

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On minimizing width in linear layouts
• Antibandwidth and cyclic antibandwidth of meshes and hypercubes
• A probabilistic heuristic for a computationally difficult set covering problem
• Optimal linear labelings and eigenvalues of graphs
• Some simplified NP-complete graph problems
• A branch and bound algorithm for the maximum diversity problem
• A branch and bound algorithm for the matrix bandwidth minimization
• Decorous Lower Bounds for Minimum Linear Arrangement
• An annotated bibliography of GRASP-Part II: Applications
• An annotated bibliography of GRASP – Part I: Algorithms
• Topological Bandwidth
• A polynomial algorithm for the min-cut linear arrangement of trees
• A Randomized Fully Polynomial Time Approximation Scheme for the All-Terminal Network Reliability Problem
• A Greedy Randomized Adaptive Search Procedure for Maximum Independent Set
• Cutwidth of the de Bruijn graph
• Optimal Linear Ordering
• Cutwidth I: A linear time fixed parameter algorithm
• Experiments on the minimum linear arrangement problem
• Optimal numberings and isoperimetric problems on graphs