|
|
|
We consider the following two problems. (i) Given a graph, add a minimum size clique to the graph such that the resulting graph is 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.
Bibtex entry:
| AUTHOR | = | {Fekete, Zsolt}, |
| TITLE | = | {Source location with rigidity and tree packing requirements}, |
| NOTE | = | {{\tt www.cs.elte.hu/egres}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2005}, |
| NUMBER | = | {TR-2005-04} |