✦ LIBER ✦

On the Parallel Complexity of Hamiltonian Cycle and Matching Problem on Dense Graphs

✍ Scribed by E. Dahlhaus; P. Hajnal; M. Karpinski

Publisher: Elsevier Science
Year: 1993
Tongue: English
Weight: 729 KB
Volume: 15
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.1993.1046

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

On the Comparison Complexity of the Stri

On the Comparison Complexity of the String Prefix-Matching Problem

✍ Dany Breslauer; Livio Colussi; Laura Toniolo 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 525 KB

In this paper we study the exact comparison complexity of the string prefixmatching problem in the deterministic sequential comparison model with equality tests. We derive almost tight lower and upper bounds on the number of symbol comparisons required in the worst case by on-line prefix-matching al

On the Approximation of Finding A(nother

On the Approximation of Finding A(nother) Hamiltonian Cycle in Cubic Hamiltonian Graphs

✍ Cristina Bazgan; Miklos Santha; Zsolt Tuza 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 144 KB

It is a simple fact that cubic Hamiltonian graphs have at least two Hamiltonian cycles. Finding such a cycle is NP-hard in general, and no polynomial-time algorithm is known for the problem of finding a second Hamiltonian cycle when one such cycle is given as part of the input. We investigate the co

On the Parallel Complexity of the Polyno

On the Parallel Complexity of the Polynomial Ideal Membership Problem

✍ Peter Bürgisser 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 457 KB

The complexity of the matching-cut probl

The complexity of the matching-cut problem for planar graphs and other graph classes

✍ Paul Bonsma 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 247 KB

## Abstract The Matching‐Cut problem is the problem to decide whether a graph has an edge cut that is also a matching. Previously this problem was studied under the name of the Decomposable Graph Recognition problem, and proved to be ${\cal{NP}}$‐complete when restricted to graphs with maximum deg

On the number of hamiltonian cycles in a

On the number of hamiltonian cycles in a maximal planar graph

✍ S. L. Hakimi; E. F. Schmeichel; C. Thomassen 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 243 KB 👁 2 views

## Abstract We consider the problem of the minimum number of Hamiltonian cycles that could be present in a Hamiltonian maximal planar graph on __p__ vertices. In particular, we construct a __p__‐vertex maximal planar graph containing exactly four Hamiltonian cycles for every __p__ ≥ 12. We also pro

On the existence of Hamiltonian cycles i

On the existence of Hamiltonian cycles in a class of random graphs

✍ T.I. Fenner; A.M. Frieze 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 468 KB

A digraph with n vertices and fixed outdegree m is generated randomly so that each such digraph is equally likely to be chosen. We consider the probability of the existence of a Hamiltonian cycle in the graph obtained by ignoring arc orientation. We show that there exists m (~23) such that a Hamilto