arXiv Open Access 2020

NP-complete variants of some classical graph problems

Per Alexandersson

Lihat Sumber

Abstrak

Some classical graph problems such as finding minimal spanning tree, shortest path or maximal flow can be done efficiently. We describe slight variations of such problems which are shown to be NP-complete. Our proofs use straightforward reduction from $3$-SAT.

Topik & Kata Kunci

cs.CC

Penulis (1)

Per Alexandersson

Format Sitasi

APA MLA BibTeX

Alexandersson, P. (2020). NP-complete variants of some classical graph problems. https://arxiv.org/abs/2001.04120

Akses Cepat

Lihat di Sumber

Informasi Jurnal

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