𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The complexity of cubical graphs

✍ Scribed by Foto Afrati; Christos H. Papadimitriou; George Papageorgiou

Book ID
114037727
Publisher
Elsevier Science
Year
1985
Weight
386 KB
Volume
66
Category
Article
ISSN
0019-9958

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

The complexity of recognizing tough cubi
The complexity of recognizing tough cubic graphs
✍ D. Bauer; J. van den Heuvel; A. Morgana; E. Schmeichel πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 647 KB

We show that it is NP-hard to determine if a cubic graph G is l-tough. We then use this result to show that for any integer t > 1, it is NP-hard to determine if a 3 t-regular graph is t-tough. We conclude with some remarks concerning the complexity of recognizing certain subclasses of tough graphs.

On the complexity of the approximation o
On the complexity of the approximation of nonplanarity parameters for cubic graphs
✍ Luerbio Faria; Celina M. Herrera de Figueiredo; Candido F.X. MendonΓ§a πŸ“‚ Article πŸ“… 2004 πŸ› Elsevier Science 🌐 English βš– 496 KB

Let G = (V; E) be a simple graph. The NON-PLANAR DELETION problem consists in ΓΏnding a smallest subset E βŠ‚ E such that H =(V; E\E ) is a planar graph. The SPLITTING NUMBER problem consists in ΓΏnding the smallest integer k ΒΏ 0, such that a planar graph H can be deΓΏned from G by k vertex splitting ope