✦ LIBER ✦

A remark on NP-completeness of picture matching

✍ Scribed by Maurizio Tucci; Gennaro Costagliola; Shi-Kuo Chang

Publisher: Elsevier Science
Year: 1991
Tongue: English
Weight: 359 KB
Volume: 39
Category: Article
ISSN: 0020-0190
DOI: 10.1016/0020-0190(91)90022-a

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

A Remark on Infinite Matching vs Infinit

A Remark on Infinite Matching vs Infinite Unification

✍ BENEDETTO INTRIGILA; MARISA VENTURINI ZILLI 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 381 KB

In this note we refine a result in Berarducci and Venturini Zilli (1993), by showing that the limit of iterations of a matching gives rise to the most general unifying substitution.

Strong NP-completeness of a matrix simil

Strong NP-completeness of a matrix similarity problem

✍ V. Brimkov; B. Codenotti; M. Leoncini; G. Resta 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 469 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

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

A remark on abstract operator completely

A remark on abstract operator completely integrable equations

✍ D.V. Chudnovsky; G.V. Chudnovsky 📂 Article 📅 1980 🏛 Elsevier Science 🌐 English ⚖ 226 KB

NP-completeness of list coloring and pre

NP-completeness of list coloring and precoloring extension on the edges of planar graphs

✍ Dániel Marx 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 110 KB

## Abstract In the edge precoloring extension problem, we are given a graph with some of the edges having preassigned colors and it has to be decided whether this coloring can be extended to a proper __k__‐edge‐coloring of the graph. In list edge coloring every edge has a list of admissible colors,