AMBIENT ASSISTED LIVING

The cost of formal health care and the caregiver burden introduced by the increasingly aging population pose a drasticchallenge to our society.The efforts to find solutions to address this issue have fostered Ambient Assisted Living(AAL)as a novel technology discipline,the aim of which is to exploit the potentials provided bythe emerginginformation and communication

Induced Subgraphs with Large Degrees at End-vertices for Hamiltonicity of Claw-free Graphs

A graph is called claw-free if it contains no induced subgrapn lsomorpmc to K1,3. Matthews and Sumner proved that a 2-connected claw-free graph G is Hamiltonian if every vertex of it has degree at least （[V（G）I - 2）/3. At the workshop CSzC （Novy Smokovec, 1993）, Broersma conjectured the degree condition of this result can be restricted only to end-vertices of induced copies of N （the graph obtained from a triangle by adding three disjoint pendant edges）. Fujisawa and Yamashita showed that the degree condition of Matthews and Sumner can be restricted only to end-vertices of induced copies of Z1 （the graph obtained from a triangle by adding one pendant edge）. Our main result in this paper is a characterization of all graphs H such that a 2-connected claw-free graph G is Hamiltonian if eachend-vertex of every induced copy of H in G has degree at least IV（G）I/3 ＋ 1. This gives an affirmative solution of the conjecture of Broersma up to an additive constant.end-vertex of every induced copy of H in G has degree at least IV（G）I/3 ＋ 1. This gives an affirmative solution of the conjecture of Broersma up to an additive constant.

On Isomorphism Testing of Groups with Normal Hall Subgroups

A normal Hall subgroup N of a group G is a normal subgroup with its order coprime with its index. Schur- Zassenhaus theorem states that every normal Hall subgroup has a complement subgroup, that is a set of coset representatives H which also forms a subgroup of G. In this paper, we present a framework to test isomorphism of groups with at least one normal Hall subgroup, when groups are given as multiplication tables. To establish the framework, we first observe that a proof of Schur-Zassenhaus theorem is constructive, and formulate a necessary and sufficient condition for testing isomorphism in terms of the associated actions of the semidirect products, and isomorphisms of the normal parts and complement parts. We then focus on the case when the normal subgroup is abelian. Utilizing basic facts of representation theory of finite groups and a technique by Le Gall （STACS 2009）, we first get an efficient isomorphism testing algorithm when the complement has bounded number of generators. For the case when the complement subgroup is elementary abelian, which does not necessarily have bounded number of generators, we obtain a polynomial time isomorphism testing algorithm by reducing to generalized code isomorphism problem, which asks whether two linear subspaces are the same up to permutation of coordinates. A solution to the latter can be obtained by a mild extension of the singly exponential （in the number of coordinates） time algorithm for code isomorphism problem developed recently by Babai et al. （SODA 2011）. Enroute to obtaining the above reduction, we study the following computational problem in representation theory of finite groups： given two representations ρandτ- of a group H over Zp^d, a prime, determine if there exists an automorphism ： ФH→ H, such that the induced representation p Ф= ρ o Ф and τ are equivalent, in time poly（｜H｜, p^d）.