Titlebook: Algorithms and Complexity; 7th International Co Tiziana Calamoneri,Josep Diaz Conference proceedings 2010 Springer-Vralg Berlin Heidelberg

Annotate

Rechnungswesen und Unternehmensüberwachungization algorithm exploits the knowledge of an optimal solution to a problem instance for finding good solutions for a locally modified instance. We show that, in graphs satisfying a sharpened triangle inequality (and even in graphs where edge-costs are restricted to the values 1 and 1 + . for an ar

清楚

,Thesenförmige Zusammenfassung,raph . = (.,.), a rational number . ≥ 1 and a weight function . on the vertices, and are asked whether a spanning tree . for . exists such that the combined weight of the leaves of . is at least .. We show that it is possible to transform an instance 〈.,., . 〉 of . in linear time into an equivalent

易于交谈

Hay-Fever

Bmd955

Polynomial Space Algorithms for Counting Dominating Sets and the Domatic Number sparse instances, we give an algorithm that counts the number of dominating sets of each size . in a graph in . time and polynomial space. We also give an algorithm for the domatic number problem running in . time and polynomial space.

antedate

Popular Matchings in the Marriage and Roommates Problems .. We investigate the relationship between popularity and stability, and describe efficient algorithms to test a matching for popularity in these settings. We also show that, when ties are permitted in the preferences, it is NP-hard to determine whether a popular matching exists in both the Roommates and Marriage cases.

collateral

有权

indignant

Die Krisis der säkularen Religionenscribing how the topology of the graph comes in to play when evaluating potential new backlinks. Based on the theorem we show that no FPTAS exists for Link Building under the assumption NP≠P and we also show that Link Building is W[1]-hard.

兽群

https://doi.org/10.1007/978-3-662-26431-7hs. We also study the parameterized complexity of their parametric dual problems. Among these sixteen problems, we show that eight of them are fixed parameter tractable and four are W[1]-hard. Our main techniques are the color-coding method of Alon, Yuster and Zwick, and the random separation method of Cai, Chan and Chan.