RUS
ENG
Full version
JOURNALS
// Zapiski Nauchnykh Seminarov POMI
// Archive
Zap. Nauchn. Sem. LOMI,
1977
Volume 68,
Pages
26–29
(Mi znsl1998)
Problem of path connections in graphs
D. Yu. Grigor'ev
Abstract:
A generalization is considered of a problem that arises in the design of electronic equipment – the tracing of printed circuits. The generalization is proved to be
$NP$
-complete in the sense sused by Cook and Karp.
UDC:
518.5,
519.1
Fulltext:
PDF file (238 kB)
English version:
Journal of Soviet Mathematics, 1981,
15
:1,
14–16
Bibliographic databases:
©
Steklov Math. Inst. of RAS
, 2024