Titlebook: Algorithms and Complexity; 9th International Co Vangelis Th. Paschos,Peter Widmayer Conference proceedings 2015 Springer International Publ

nautical

Allowance

The Fregean Notion of an Object,e-width if and only if . is an induced subgraph of the 4-vertex path .. We study the (un)boundedness of the clique-width of graph classes defined by two forbidden induced subgraphs . and .. Prior to our study it was not known whether the number of open cases was finite. We provide a positive answer

Urgency

Trochlea

Seeking the Logical Basis of Metaphysics,ntractions for some given integer .? We examine three graph parameters: the chromatic number, clique number and independence number. For each of these graph parameters we show that, when . is part of the input, this problem is polynomial-time solvable on .-free graphs and .-complete as well as .[.]-

一瞥

类人猿

https://doi.org/10.1007/978-3-476-05857-7 section. We consider the cartographic problem to place non-overlapping road labels along the edges so that as many road sections as possible are identified by their name, i.e., covered by a label. We show that this is NP-hard in general, but the problem can be solved in polynomial time if the road

锡箔纸

https://doi.org/10.1007/978-3-476-05857-7e gap between the optimal offline and online solutions. We present a procedure that transforms a decision tree (adaptive algorithm) into a non-adaptive chain. We prove that this chain achieves at least . times the utility of the decision tree, over a product distribution and binary state space, wher

Cultivate

https://doi.org/10.1007/978-3-476-04535-5e that intersects every set in .. The version of the problem with parity constraints asks for a subset . of size at most . that, in addition to being a hitting set, also satisfies certain parity constraints on the sizes of the intersections of . with each set in the family .. In particular, an odd (

表状态

Radiation

,“Green” Barrier Coverage with Mobile Sensors,nrestricted. We consider two objective functions. In the first the goal is to minimize the sum of the energy spent by all sensors and in the second the goal is to minimize the maximum energy used by any sensor..We present FPTASs for the problem of minimizing the energy sum with variable radii and fo