𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Strong NP-completeness of a matrix similarity problem

✍ Scribed by V. Brimkov; B. Codenotti; M. Leoncini; G. Resta

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
469 KB
Volume
165
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

NP completeness of the edge precoloring
NP completeness of the edge precoloring extension problem on bipartite graphs
✍ JiΕ™Γ­ Fiala πŸ“‚ Article πŸ“… 2003 πŸ› John Wiley and Sons 🌐 English βš– 63 KB πŸ‘ 1 views

## Abstract We show that the following problem is __NP__ complete: Let __G__ be a cubic bipartite graph and __f__ be a precoloring of a subset of edges of __G__ using at most three colors. Can __f__ be extended to a proper edge 3‐coloring of the entire graph __G__? This result provides a natural co

On a Class of Matrix Completion Problems
On a Class of Matrix Completion Problems
✍ Vladimir K. Dubovoj; Bernd Fritzsche; Bernd Kirstein πŸ“‚ Article πŸ“… 1989 πŸ› John Wiley and Sons 🌐 English βš– 618 KB
On the np-completeness of certain networ
On the np-completeness of certain network testing problems
✍ S. Even; O. Goldreich; S. Moran; P. Tong πŸ“‚ Article πŸ“… 1984 πŸ› John Wiley and Sons 🌐 English βš– 946 KB

Let G ( V , E) be an undirected graph which describes the structure of a communication network. During the maintenance period every line must be tested in each of the two possible directions. A line is tested by assigning one of its endpoints t o be a transmitter, the other to be a receiver, and sen