dc.contributor |
Universitat Politècnica de Catalunya. Departament de Llenguatges i Sistemes Informàtics |
dc.contributor.author |
Fomin, Fedor V. |
dc.contributor.author |
Fraigniaud, Pierre |
dc.contributor.author |
Thilikos Touloupas, Dimitrios |
dc.date |
2004-05 |
dc.identifier.citation |
Fomin, F., Fraigniaud, P., Thilikos, D. "The price of connectedness in expansions". 2004. |
dc.identifier.uri |
http://hdl.handle.net/2117/98590 |
dc.language.iso |
eng |
dc.relation |
R04-28 |
dc.rights |
info:eu-repo/semantics/openAccess |
dc.subject |
Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica |
dc.subject |
Branchwidth |
dc.subject |
Pathwidth |
dc.subject |
Expansion |
dc.subject |
Graph searching |
dc.title |
The price of connectedness in expansions |
dc.type |
info:eu-repo/semantics/publishedVersion |
dc.type |
info:eu-repo/semantics/report |
dc.description.abstract |
Expansion is the way of generalizing different graph layout and
searching problems. We initiate the study of connected expansion which
naturally arises in a number of applications. Our main tool for this
investigation is the branchwidth of a graph. In particular, we prove
that any 2-edge-connected graph of branchwidth k has a {em
connected} branch decom-po-si-tion of width k, i.e., a branch
decomposition in which any cut separates two edge-sets that induce two
connected subgraphs. Our proof is constructive, and is inspired from
the existential proof of Seymour and Thomas (1994) for carvings. We
also prove that the {em connected} search number (i.e., connected
pathwidth) of any n-node graph of branchwidth k is at most
O(klog n) and this bound is the best possible for parameters k
and n. A first consequence of these results is that, for any graph,
the connected search number is at most O(log n) times larger than
the (standard) search number. The only bound known so far held for
trees only. Another consequence is that the connected search number
can be approximated in polynomial time up to a factor
O(log{n}cdotlog{OPT}). That is, for any connected graph G, one
can compute in polynomial time a connected search strategy for G
that uses at most O (log{n}cdotlog{OPT}) times the optimal number
OPT of searchers. The ratio O(log{n}cdotlog{OPT}) is the same
as the best known approximation ratio for (standard) pathwidth, and
any improvement for the approximation of connected search (i.e.,
connected pathwidth) would indeed produce an improvement for the
approximation of pathwidth. |