TR-2005-04

Source location with rigidity and tree packing requirements

Zsolt Fekete



Abstract

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:

@techreport{egres-05-04,
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}
}


Last modification: 21.7.2014. Please email your comments to Jácint Szabó!