𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A polynomial time algorithm recognizing link trees

✍ Scribed by Peter Bugata; Attila Nagy; Roman Vávra

Publisher
John Wiley and Sons
Year
1995
Tongue
English
Weight
672 KB
Volume
19
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

The link of a vertex u of a graph G is the subgraph induced by all vertices adjacent to u . If all the links of G are isomorphic to a finite graph L, then G is called a realization of L, and L is called a link graph.

At the Smolenice symposium of 1963, Zykov posed the problem of recognizing iink graphs. There are two versions of that problem, namely the finite (the existence of a finite realization is required) and the infinite one.

Bulitko (see "On Graphs with Prescribed Links of Vertices" [in

📜 SIMILAR VOLUMES

A polynomial time algorithm for rectilin
A polynomial time algorithm for rectilinear Steiner trees with terminals constrained to curves
✍ Brazil, M.; Thomas, D. A.; Weng, J. F. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 168 KB 👁 2 views

The rectilinear Steiner problem is the problem of constructing the shortest rectilinear network in the plane connecting a given set of points, called terminals. The problem is known to be NP-complete in general. In this paper, we show that there is a polynomial time algorithm for solving the rectili

A polynomial time circle packing algorit
A polynomial time circle packing algorithm
✍ Bojan Mohar 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 428 KB

Mohar, B., A polynomial time circle packing algorithm, Discrete Mathematics 117 (1993) 2577263. The Andreev-Koebe-Thurston circle packing theorem is generalized and improved in two ways. Simultaneous circle packing representations of the map and its dual map are obtained such that any two edges dua

A Polynomial-Time Parsing Algorithm forK
A Polynomial-Time Parsing Algorithm forK-Depth Languages
✍ Alessandra Cherubini; Pierluigi San Pietro 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 736 KB

K-depth grammars extend context-free grammars allowing k 1 rewriting points for a single non-terminal at every step of a derivation. The family of languages generated by k-depth grammars is a proper extension of the family of context-free languages, while retaining many context-free properties, such

A polynomial algorithm for thep-centdian
A polynomial algorithm for thep-centdian problem on a tree
✍ Tamir, Arie; P�rez-Brito, Dionisio; Moreno-P�rez, Jos� A. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 108 KB 👁 2 views

The most common problems studied in network location theory are the p-median and the p-center models. The p-median problem on a network is concerned with the location of p points (medians) on the network, such that the total (weighted) distance of all the nodes to their respective nearest points is

A linear time algorithm to recognize cir
A linear time algorithm to recognize circular permutation graphs
✍ Sritharan, R. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 368 KB

An undirected graph G is a circular permutation graph if it can be represented by the following intersectiori model: Each vertex of G corresponds to a chord in the annular region between two concentric circles, and two vertices are adjacent in G if and only if their corresponding chords intersect ea