Branch and bound for the cutwidth minimization problem

DOI10.1016/J.COR.2012.05.016MaRDI QIDQ339558zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Rafael Martí, Juan J. Pantrigo, Abraham Duarte, Eduardo G. Pardo

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) Graph algorithms (graph-theoretic aspects) (05C85) Integer programming (90C10) Connectivity (05C40)

Recommendations

• A branch-and-bound algorithm for the minimum cut linear arrangement problem
• A variable neighbourhood search approach to the cutwidth minimization problem
• Scatter search for the cutwidth minimization problem
• Tailored heuristics in adaptive large neighborhood search applied to the cutwidth minimization problem
• Multistart search for the cyclic cutwidth minimization problem

Cites work

• scientific article; zbMATH DE number 3174052 (Why is no real title available?)
• scientific article; zbMATH DE number 1062113 (Why is no real title available?)
• scientific article; zbMATH DE number 2050708 (Why is no real title available?)
• A Greedy Randomized Adaptive Search Procedure for Maximum Independent Set
• A Randomized Fully Polynomial Time Approximation Scheme for the All-Terminal Network Reliability Problem
• A branch and bound algorithm for the matrix bandwidth minimization
• A branch and bound algorithm for the maximum diversity problem
• A polynomial algorithm for the min-cut linear arrangement of trees
• A probabilistic heuristic for a computationally difficult set covering problem
• An annotated bibliography of GRASP – Part I: Algorithms
• An annotated bibliography of GRASP-Part II: Applications
• Antibandwidth and cyclic antibandwidth of meshes and hypercubes
• Cutwidth I: A linear time fixed parameter algorithm
• Cutwidth of the de Bruijn graph
• Decorous lower bounds for minimum linear arrangement
• Experiments on the minimum linear arrangement problem
• On minimizing width in linear layouts
• Optimal Linear Ordering
• Optimal linear labelings and eigenvalues of graphs
• Optimal numberings and isoperimetric problems on graphs
• Some simplified NP-complete graph problems
• Topological Bandwidth

Cited in

(13)

• Lower bounds for the bandwidth problem
• Multistart search for the cyclic cutwidth minimization problem
• Tailored heuristics in adaptive large neighborhood search applied to the cutwidth minimization problem
• Strong SDP based bounds on the cutwidth of a graph
• Computing tight bounds via piecewise linear functions through the example of circle cutting problems
• Optimization procedures for the bipartite unconstrained 0-1 quadratic programming problem
• A note on computational approaches for the antibandwidth problem
• A branch-and-bound algorithm for the minimum cut linear arrangement problem
• Efficient iterated greedy for the two-dimensional bandwidth minimization problem
• Theoretical lower bound for border length minimization problem
• Scatter search for the cutwidth minimization problem
• A variable neighbourhood search approach to the cutwidth minimization problem
• New lower bounds on the cutwidth of graphs

Describes a project that uses

Uses Software

• Tabu search
• CPLEX
• GRASP

This page was built for publication: Branch and bound for the cutwidth minimization problem

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