000171387 001__ 171387
000171387 005__ 20181203022532.0
000171387 0247_ $$2doi$$a10.1016/j.cor.2011.02.016
000171387 02470 $$2ISI$$a000290932100011
000171387 037__ $$aARTICLE
000171387 245__ $$aComplexity of the critical node problem over trees
000171387 269__ $$a2011
000171387 260__ $$c2011
000171387 336__ $$aJournal Articles
000171387 520__ $$aIn this paper we deal with the critical node problem (CNP), i.e., the problem of searching for a given number K of nodes in a graph G, whose removal minimizes the (weighted or unweighted) number of connections between pairs of nodes in the residual graph. In particular, we study the case where the physical network represented by graph G has a hierarchical organization, so that G is a tree. The NP-completeness of this problem for general graphs has been already established (Arulselvan et al.). We study the subclass of CNP over trees, generalizing the objective function and constraints to take into account general nonnegative "costs" of node connections and "weights" for the nodes that are to be removed. We prove that CNP over trees is still NP-complete when general connection costs are specified, while the cases where all connections have unit cost are solvable in polynomial time by dynamic programming approaches. For the case with nonnegative connection costs and unit node weights we propose an enumeration scheme whose time complexity is within a polynomial factor from 0(1.618034"), where n is the number of nodes of the tree. Results from computational experiments are reported for all the proposed algorithms. (C) 2011 Elsevier Ltd. All rights reserved.
000171387 6531_ $$aComplexity
000171387 6531_ $$aCritical node problem
000171387 6531_ $$aMulticut in trees
000171387 6531_ $$aDynamic programming
000171387 700__ $$0245134$$g210336$$aDi Summa, Marco
000171387 700__ $$aGrosso, Andrea
000171387 700__ $$aLocatelli, Marco
000171387 773__ $$j38$$tComputers & Operations Research$$q1766-1774
000171387 909C0 $$xU11879$$0252111$$pDISOPT
000171387 909CO $$pSB$$particle$$ooai:infoscience.tind.io:171387
000171387 917Z8 $$x183121
000171387 937__ $$aEPFL-ARTICLE-171387
000171387 973__ $$rREVIEWED$$sPUBLISHED$$aOTHER
000171387 980__ $$aARTICLE