Lam, Fumei and Pachter, Lior (2003) Forcing numbers of stop signs. Theoretical Computer Science, 303 (2-3). pp. 409-416. ISSN 0304-3975. doi:10.1016/S0304-3975(02)00499-1. https://resolver.caltech.edu/CaltechAUTHORS:20170308-151538288
Full text is not posted in this repository. Consult Related URLs below.
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20170308-151538288
Abstract
Let G be a graph with a perfect matching M. The forcing number of M is the smallest number of edges in a subset S⊂M such that S is contained in no other perfect matching of G. We present methods for determining bounds on forcing numbers and apply these methods to find bounds for the forcing numbers of stop signs. A consequence of our main result is that every perfect matching of a stop sign of size (n,k) contains at least n disjoint alternating cycles.
| Item Type: | Article | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Related URLs: |
| |||||||||
| ORCID: |
| |||||||||
| Additional Information: | © 2002 Elsevier. | |||||||||
| Issue or Number: | 2-3 | |||||||||
| DOI: | 10.1016/S0304-3975(02)00499-1 | |||||||||
| Record Number: | CaltechAUTHORS:20170308-151538288 | |||||||||
| Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20170308-151538288 | |||||||||
| Official Citation: | Fumei Lam, Lior Pachter, Forcing numbers of stop signs, Theoretical Computer Science, Volume 303, Issue 2, 2003, Pages 409-416, ISSN 0304-3975, http://dx.doi.org/10.1016/S0304-3975(02)00499-1. (http://www.sciencedirect.com/science/article/pii/S0304397502004991) | |||||||||
| Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | |||||||||
| ID Code: | 74931 | |||||||||
| Collection: | CaltechAUTHORS | |||||||||
| Deposited By: | George Porter | |||||||||
| Deposited On: | 09 Mar 2017 15:38 | |||||||||
| Last Modified: | 15 Nov 2021 16:29 |
Repository Staff Only: item control page
