arXiv Open Access 2023

A Note on the Complexity of One-Sided Crossing Minimization of Trees

Alexander Dobler

Lihat Sumber

Abstrak

In 2011, Harrigan and Healy published a polynomial-time algorithm for one-sided crossing minimization for trees. We point out a counterexample to that algorithm, and show that one-sided crossing minimization is NP-hard for trees.

Topik & Kata Kunci

cs.CC

Penulis (1)

Alexander Dobler

Format Sitasi

APA MLA BibTeX

Dobler, A. (2023). A Note on the Complexity of One-Sided Crossing Minimization of Trees. https://arxiv.org/abs/2306.15339

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2023
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓