✦ LIBER ✦

Efficient Algorithms for Petersen's Matching Theorem

✍ Scribed by Therese C. Biedl; Prosenjit Bose; Erik D. Demaine; Anna Lubiw

Publisher: Elsevier Science
Year: 2001
Tongue: English
Weight: 293 KB
Volume: 38
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.2000.1132

No coin nor oath required. For personal study only.

✦ Synopsis

Petersen's theorem is a classic result in matching theory from 1891, stating that every 3-regular bridgeless graph has a perfect matching. Our work explores efficient algorithms for finding perfect matchings in such graphs. Previously, the only relevant matching algorithms were for general graphs, and the fastest algo-Ž 3r 2 . rithm ran in O n time for 3-regular graphs. We have developed an Ž 4 . O n log n -time algorithm for perfect matching in a 3-regular bridgeless graph. When the graph is also planar, we have as the main result of our paper an optimal Ž . O n -time algorithm. We present three applications of this result: terrain guarding, adaptive mesh refinement, and quadrangulation.

📜 SIMILAR VOLUMES

Efficient Algorithms for Approximate Str

Efficient Algorithms for Approximate String Matching with Swaps

✍ Dong Kyue Kim; Jee-Soo Lee; Kunsoo Park; Yookun Cho 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 357 KB

A reduction theorem for normal algorithm

A reduction theorem for normal algorithms

✍ R. M. Baer 📂 Article 📅 1969 🏛 John Wiley and Sons 🌐 English ⚖ 210 KB

An Efficient Parallel Algorithm for Maxi

An Efficient Parallel Algorithm for Maximum Matching for Some Classes of Graphs

✍ I. Parfenoff 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 403 KB

The P 4 -tidy graphs were introduced by I. Rusu to generalize some already known classes of graphs with few induced P 4 (cographs, P 4 -sparse graphs, P 4 -lite graphs). Here, we propose an extension of R. Lin and S. Olariu's work (1994. J. Parallel Distributed Computing 22, 26 36.) on cographs, usi

A matching theorem for locally stationar

A matching theorem for locally stationary random processes

✍ Richard A. Silverman 📂 Article 📅 1959 🏛 John Wiley and Sons 🌐 English ⚖ 605 KB

Generic VLSI architecture for block-matc

Generic VLSI architecture for block-matching motion estimation algorithms

✍ Zhong L. He; Ming L. Liou; Philip. C. H. Chan; C. Y. Tsui 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 403 KB

In this article, a generic VLSI architecture which is both a switch network to implement two block-matching motion estiprogrammable and scalable is proposed for block-matching motion mation algorithms: namely, full-search and three-step search, estimation algorithms. Various motion estimation algori

Fast and Robust Stereo Matching Algorith

Fast and Robust Stereo Matching Algorithms for Mining Automation

✍ Jasmine Banks; Mohammed Bennamoun; Peter Corke 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 184 KB

The mining environment, being complex, irregular, and time-varying, presents a challenging prospect for stereo vision. For this application, speed, reliability, and the ability to produce a dense depth map are of foremost importance. This paper evaluates a number of matching techniques for possible