An SDP approach to multi-level crossing minimization

DOI10.1145/2133803.2330084MaRDI QIDQ5406272zbMATH OpenOpenAlexFDO

Authors Markus Chimani, Philipp Hungerländer, Michael Jünger, Petra Mutzel

Publication date 1 April 2014

Published in ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL http://e-archive.informatik.uni-koeln.de/616/2/zaik2011-616.pdf

zbMATH Keywords

exact multi-level crossing minimizationexperimental evaluationSDP approachSugiyama

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Linear programming (90C05) Integer programming (90C10) Semidefinite programming (90C22) Combinatorial optimization (90C27)

Recommendations

• An SDP approach to multi-level crossing minimization
• scientific article; zbMATH DE number 1487879
• scientific article; zbMATH DE number 1500682
• A New Approach to Exact Crossing Minimization
• Parameterized analysis and crossing minimization problems
• An alternative method to crossing minimization on hierarchical graphs
• A faster fixed parameter algorithm for two-layer crossing minimization
• scientific article; zbMATH DE number 1109408
• Recent advances in exact crossing minimization (extended abstract)
• scientific article; zbMATH DE number 7525513

Cited in

(5)

• Hybridizing simulated annealing with variable neighborhood search for bipartite graph crossing minimization
• Crossing Minimization in Storyline Visualization
• An SDP approach to multi-level crossing minimization
• Semidefinite relaxations for partitioning, assignment and ordering problems
• A linear edge kernel for two-layer crossing minimization

Describes a project that uses

Uses Software

• Biq Mac

This page was built for publication: An SDP approach to multi-level crossing minimization

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