A branch and bound algorithm for minimizing the number of crossing arcs in bipartite graphs

DOI10.1016/0377-2217(95)00356-8MaRDI QIDQ1266546zbMATH OpenOpenAlexFDO

Authors Vicente Valls, Rafael Martí, Pilar Lino

Publication date 7 October 1998

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0377-2217(95)00356-8

zbMATH Keywords

acyclic directed graphsautomatic graph drawingbipartite graphsbranch-and-boundcrossing arcs minimization

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Recommendations

• A tabu thresholding algorithm for arc crossing minimization in bipartite graphs
• scientific article; zbMATH DE number 1054930
• A tabu search algorithm for the bipartite drawing problem
• Edge crossings in drawings of bipartite graphs
• ARC crossing minimization in hierarchical digraphs with tabu search

Cites work

• Algorithms for drawing graphs: An annotated bibliography
• Crossing Theory and Hierarchy Mapping
• Experiments on drawing 2-level hierarchical graphs
• Hierarchies and planarity theory
• scientific article; zbMATH DE number 3963860 (Why is no real title available?)
• scientific article; zbMATH DE number 3573250 (Why is no real title available?)
• The NP-completeness column: An ongoing gulde

Cited in

(15)

• Crossing minimization in weighted bipartite graphs
• ARC crossing minimization in hierarchical digraphs with tabu search
• A tabu search algorithm for the bipartite drawing problem
• Heuristics and meta-heuristics for 2-layer straight line crossing minimization
• A tabu thresholding algorithm for arc crossing minimization in bipartite graphs
• Hybridizing simulated annealing with variable neighborhood search for bipartite graph crossing minimization
• A rearrangement of adjacency matrix based approach for solving the crossing minimization problem
• 2-layer right angle crossing drawings
• Crossing Minimization in Weighted Bipartite Graphs
• Incremental bipartite drawing problem
• Drawing graphs with k vertices per face: complexity and algorithms
• On the complexity of recognizing k^+-real face graphs
• Quantum algorithms for one-sided crossing minimization
• Quantum algorithms for one-sided crossing minimization
• Crossing minimization in extended level drawings of graphs

This page was built for publication: A branch and bound algorithm for minimizing the number of crossing arcs in bipartite graphs

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