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

严厉谴责

Clique-Width of Graph Classes Defined by Two Forbidden Induced Subgraphs,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

ineptitude

Randomized Adaptive Test Cover, an unknown target element using a minimum number of tests. We explore the expected test number of randomized strategies. We obtain several general results on the ratio of the expected and worst-case deterministic test number, as well as complexity results for hypergraphs of small rank, and we state

Amnesty

变色龙

On the Complexity of Wafer-to-Wafer Integration,. disjoints sets (called “lots”), where each set contains . wafers. The output of the problem is a set of . disjoint stacks, where a stack is a set of . wafers (one wafer from each lot). To each stack we associate a .-dimensional binary vector corresponding to the bit-wise AND operation of the wafer

掺和

Label Placement in Road Maps, 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

intertwine

Discrete Stochastic Submodular Maximization: Adaptive vs. Non-adaptive vs. Offline,e 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

Eulogy

enhance

Simple Strategies Versus Optimal Schedules in Multi-agent Patrolling, an agent at least once in every unit time period. A simple strategy where the .th agent moves back and forth in a segment of length . patrols the length ., but it has been shown recently that this is not always optimal. Thus a natural question is to determine the smallest . such that a fence of len

Peak-Bone-Mass

Communication, Dynamics, and Renormalization, of graphs over a given set of nodes. The technique is then harnessed to carry out a dynamic form of renormalization for averaging-based systems. This analytical framework allows us to formulate new criteria for ensuring the asymptotic periodicity of diffusive influence systems.

等待