Titlebook: Algorithms - ESA 2007; 15th Annual European Lars Arge,Michael Hoffmann,Emo Welzl Conference proceedings 2007 Springer-Verlag Berlin Heidelb

设想

拍下盗公款

创造性

Polynomial Time Algorithms for Minimum Energy Schedulinge. One common method for saving energy is to simply suspend the system during the idle times. No energy is consumed in the suspend mode. However, the process of waking up the system itself requires a certain fixed amount of energy, and thus suspending the system is beneficial only if the idle time i

潜移默化

挡泥板

Finding Branch-Decompositions and Rank-Decompositions an input matroid represented over a fixed finite field, outputs its branch-decomposition of width at most . if such exists. This algorithm works also for partitioned matroids. Both these algorithms are fixed-parameter tractable, that is, they run in time .(..) for each fixed value of . where . is t

BRUNT

Fast Algorithms for Maximum Subset Matching and All-Pairs Shortest Paths in Graphs with a (Not So) Sr of vertices of . that can be matched in a matching of .. Our first result is a new randomized algorithm for the Maximum Subset Matching problem that improves upon the fastest known algorithms for this problem. Our algorithm runs in . time if . ≥ .. and in . time if . ≤ .., where .< 2.376 is the ma

–FER

Radix Sorting with No Extra Spacerange [1,.] can be sorted in . time [5]. However, these algorithms use .(.) words of extra memory. Is this necessary?.We present a simple, stable, integer sorting algorithm for words of size .(log.), which works in .(.) time and uses only .(1) words of extra memory on a RAM model. This is the intege

GUILE

芦笋

978-3-540-75519-7Springer-Verlag Berlin Heidelberg 2007

冰雹

https://doi.org/10.1007/978-3-642-76317-5or small enough (additive) . — and hence, presumably, an intractable problem. This solved a long-standing open problem in Algorithmic Game Theory, but created many open questions. For example, it is known that inverse polynomial . is enough to make the problem intractable, while, for two player game