Crossing minimization in weighted bipartite graphs

DOI10.1016/J.JDA.2008.08.003MaRDI QIDQ1044030zbMATH OpenOpenAlexFDO

Authors Olca A. Çakıroḡlu, Cesim Erten, Ömer Karataş, Melih Sözdinler

Publication date 10 December 2009

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2008.08.003

zbMATH Keywords

approximation algorithmscombinatorial optimizationcrossing minimizationweighted bipartite graphs

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Crossing Minimization in Weighted Bipartite Graphs
• On the one-sided crossing minimization in a bipartite graph with large degrees
• Crossing minimization in linear embeddings of graphs
• Maximum weighted matching with few edge crossings for 2-layered bipartite graph
• A branch and bound algorithm for minimizing the number of crossing arcs in bipartite graphs
• Minimizing maximum weight of subsets of a maximum matching in a bipartite graph
• Graph Bipartization and via minimization
• Crossing and Weighted Crossing Number of Near-Planar Graphs
• An alternative method to crossing minimization on hierarchical graphs

Cites work

• 2-Layer Straightline Crossing Minimization: Performance of Exact and Heuristic Algorithms
• An improved bound on the one-sided minimum crossing number in two-layered drawings
• Breaking cycles for minimizing crossings
• Crossing Number is NP-Complete
• Crossing Theory and Hierarchy Mapping
• Edge crossings in drawings of bipartite graphs
• Graph Drawing
• Graph Drawing
• Heuristics, experimental subjects, and treatment evaluation in bigraph crossing minimization
• scientific article; zbMATH DE number 2084271 (Why is no real title available?)
• scientific article; zbMATH DE number 437527 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1974127 (Why is no real title available?)
• scientific article; zbMATH DE number 1796980 (Why is no real title available?)
• scientific article; zbMATH DE number 1368469 (Why is no real title available?)
• scientific article; zbMATH DE number 764413 (Why is no real title available?)
• New bounds on the barycenter heuristic for bipartite graph drawing.

Cited in

(9)

• On the one-sided crossing minimization in a bipartite graph with large degrees
• A tabu thresholding algorithm for arc crossing minimization in bipartite graphs
• Maximum weighted matching with few edge crossings for 2-layered bipartite graph
• A variable depth neighborhood search algorithm for the min-max arc crossing problem
• On bipartite drawings and the linear arrangement problem
• A rearrangement of adjacency matrix based approach for solving the crossing minimization problem
• On bipartite crossings, largest biplanar subgraphs, and the linear arrangement problem
• Crossing Minimization in Weighted Bipartite Graphs
• Width notions for ordering-related problems

Describes a project that uses

Uses Software

• GraphBase
• LEDA
• visone
• GSL

This page was built for publication: Crossing minimization in weighted bipartite graphs

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