| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 1143263 | Operations Research Letters | 2006 | 6 Pages |
Abstract
We consider the following two problems: (i) given a graph, find a minimum size vertex-set such that the pinning of it makes the graph rigid in the plane. (ii) Given a graph, contract a minimum size vertex-set such that the resulting graph has two edge-disjoint spanning trees. We prove that these problems are polynomially solvable.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Zsolt Fekete,