Hybridizing simulated annealing with variable neighborhood search for bipartite graph crossing minimization

DOI10.1016/J.AMC.2018.11.051MaRDI QIDQ2008804zbMATH OpenOpenAlexWikidataFDO

Authors Arūnas Tomkevičius, Armantas Ostreika, Gintaras Palubeckis

Publication date 26 November 2019

Published in Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.amc.2018.11.051

zbMATH Keywords

simulated annealingcombinatorial optimizationvariable neighborhood searchedge crossing minimization

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• A variable neighborhood search and simulated annealing hybrid for the profile minimization problem
• A tabu search algorithm for the bipartite drawing problem
• scientific article; zbMATH DE number 1054930
• A New Exact Algorithm for the Two-Sided Crossing Minimization Problem
• A rearrangement of adjacency matrix based approach for solving the crossing minimization problem

Cites work

• scientific article; zbMATH DE number 2123123 (Why is no real title available?)
• scientific article; zbMATH DE number 4174847 (Why is no real title available?)
• scientific article; zbMATH DE number 3963860 (Why is no real title available?)
• scientific article; zbMATH DE number 4094839 (Why is no real title available?)
• scientific article; zbMATH DE number 1974130 (Why is no real title available?)
• scientific article; zbMATH DE number 3412664 (Why is no real title available?)
• 2-Layer Straightline Crossing Minimization: Performance of Exact and Heuristic Algorithms
• A New Exact Algorithm for the Two-Sided Crossing Minimization Problem
• A SPECIAL CROSSING NUMBER FOR BIPARTITE GRAPHS: A RESEARCH PROBLEM
• A branch and bound algorithm for minimizing the number of crossing arcs in bipartite graphs
• A dual representation simulated annealing algorithm for the bandwidth minimization problem on graphs
• A faster fixed parameter algorithm for two-layer crossing minimization
• A linear edge kernel for two-layer crossing minimization
• A new lower bound for the bipartite crossing number with applications
• A rearrangement of adjacency matrix based approach for solving the crossing minimization problem
• A tabu search algorithm for the bipartite drawing problem
• A tabu thresholding algorithm for arc crossing minimization in bipartite graphs
• A variable neighborhood search and simulated annealing hybrid for the profile minimization problem
• ARC crossing minimization in hierarchical digraphs with tabu search
• An SDP approach to multi-level crossing minimization
• An effective two-stage simulated annealing algorithm for the minimum linear arrangement problem
• Bipartite permutation graphs
• Comparing trees via crossing minimization
• Crossing Number is NP-Complete
• DAG—a program that draws directed graphs
• Edge crossings in drawings of bipartite graphs
• Exact algorithms for the quadratic linear ordering problem
• Experiments on drawing 2-level hierarchical graphs
• Fast local search for single row facility layout
• GRASP and Path Relinking for 2-Layer Straight Line Crossing Minimization
• Generalized \(k\)-ary tanglegrams on level graphs: a satisfiability-based approach and its evaluation
• Graph Drawing
• Heuristics and meta-heuristics for 2-layer straight line crossing minimization
• Heuristics, experimental subjects, and treatment evaluation in bigraph crossing minimization
• Incremental bipartite drawing problem
• New lower bound techniques for VLSI
• On bipartite drawings and the linear arrangement problem
• Optimization by simulated annealing
• Robust clustering by double bisection crossing minimization
• Simple and Efficient Bilayer Cross Counting
• Tabu search for the dynamic bipartite drawing problem
• Thermodynamical approach to the travelling salesman problem: An efficient simulation algorithm
• Trees with Hamiltonian square
• Variable neighborhood scatter search for the incremental graph drawing problem
• Variable neighborhood search: Principles and applications
• Variable neighbourhood search for bandwidth reduction
• Variable neighbourhood search: methods and applications

Cited in

(3)

• A variable depth neighborhood search algorithm for the min-max arc crossing problem
• A variable neighborhood search and simulated annealing hybrid for the profile minimization problem
• Subnetwork constraints for tighter upper bounds and exact solution of the clique partitioning problem

This page was built for publication: Hybridizing simulated annealing with variable neighborhood search for bipartite graph crossing minimization

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