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


 English version:
Journal of Soviet Mathematics, 1981, 15:1, 14–16

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024