Conjectured in 1943, Hadwiger’s conjecture is one of the most challenging open problems in graph theory. Hadwiger’s conjecture states that if the chromatic number of a graph G is k, then G has a clique minor of size at least k. In this thesis, we give motivation for attempting Hadwiger’s conjecture for circular arc graphs and also prove the conjecture for proper circular arc graphs. Circular arc graphs are graphs whose vertices can be represented as arcs on a circle such that any two vertices are adjacent if and only if their corresponding arcs intersect. Proper circular arc graphs are a subclass of circular arc graphs that have a circular arc representation where no arc is completely contained in any other arc. It is interesting to study Hadwiger’s conjecture for circular arc graphs as their clique minor cannot exceed beyond a constant factor of its chromatic number as We show in this thesis. Our main contribution is the proof of Hadwiger’s conjecture for proper circular arc graphs. Also, in this thesis we give an analysis and some basic results on Hadwiger’s conjecture for circular arc graphs in general.

In this thesis, we show results for some well-studied problems from learning theory and combinatorial optimization. Learning Parities under the Uniform Distribution: We study the learnability of parities in the agnostic learning framework of Haussler and Kearns et al. We show that under the uniform distribution, agnostically learning parities reduces to learning parities with random classification noise, commonly referred to as the noisy parity problem. Together with the parity learning algorithm of Blum et al, this gives the first nontrivial algorithm for agnostic learning of parities. We use similar techniques to reduce learning of two other fundamental concept classes under the uniform distribution to learning of noisy parities. Namely, we show that learning of DNF expressions reduces to learning noisy parities of just logarithmic number of variables and learning of k-juntas reduces to learning noisy parities of k variables. Agnostic Learning of Halfspaces: We give an essentially optimal hardness result for agnostic learning of halfspaces over rationals. We show that for any constant ε finding a halfspace that agrees with an unknown function on 1/2+ε fraction of examples is NP-hard even when there exists a halfspace that agrees with the unknown function on 1-ε fraction of examples. This significantly improves on a number of previous hardness results for this problem. We extend the result to ε = 2[superscript-Ω(sqrt{log n})] assuming NP is not contained in DTIME(2[superscript(log n)O(1)]). Majorities of Halfspaces: We show that majorities of halfspaces are hard to PAC-learn using any representation, based on the cryptographic assumption underlying the Ajtai-Dwork cryptosystem. This also implies a hardness result for learning halfspaces with a high rate of adversarial noise even if the learning algorithm can output any efficiently computable hypothesis. Max-Clique, Chromatic Number and Min-3Lin-Deletion: We prove an improved hardness of approximation result for two problems, namely, the problem of finding the size of the largest clique in a graph (also referred to as the Max-Clique problem) and the problem of finding the chromatic number of a graph. We show that for any constant γ > 0, there is no polynomial time algorithm that approximates these problems within factor n/2[superscript(log n)3/4+γ] in an n vertex graph, assuming NP is not contained in BPTIME(2[superscript(log n)O(1)]). This improves the hardness factor of n/2[superscript (log n)1-γ'] for some small (unspecified) constant γ' > 0 shown by Khot. Our main idea is to show an improved hardness result for the Min-3Lin-Deletion problem. An instance of Min-3Lin-Deletion is a system of linear equations modulo 2, where each equation is over three variables. The objective is to find the minimum number of equations that need to be deleted so that the remaining system of equations has a satisfying assignment. We show a hardness factor of 2[superscript sqrt{log n}] for this problem, improving upon the hardness factor of (log n)[superscriptβ] shown by Hastad, for some small (unspecified) constant β > 0. The hardness results for Max-Clique and chromatic number are then obtained using the reduction from Min-3Lin-Deletion as given by Khot. Monotone Multilinear Boolean Circuits for Bipartite Perfect Matching: A monotone Boolean circuit is said to be multilinear if for any AND gate in the circuit, the minimal representation of the two input functions to the gate do not have any variable in common. We show that monotone multilinear Boolean circuits for computing bipartite perfect matching require exponential size. In fact we prove a stronger result by characterizing the structure of the smallest monotone multilinear Boolean circuits for the problem.

<p>Denote by $k_t(G)$ the number of cliques of order $t$ in a graph $G$ having $n$ vertices. Let $k_t(n) = \min\{k_t(G)+k_t(\overline{G}) \}$ where $\overline{G}$ denotes the complement of $G$. Let $c_t(n) = {k_t(n)}/{\tbinom{n}{t}}$ and $c_t$ be the limit of $c_t(n)$ for $n$ going to infinity. A 1962 conjecture of Erd\H{o}s stating that $c_t = 2^{1-\tbinom{t}{2}}$ was disproved by Thomason in 1989 for all $t\geq 4$. Tighter counterexamples have been constructed by Jagger, {\v S}{\v t}ov{\' \i}{\v c}ek and Thomason in 1996, by Thomason for $t\leq 6$ in 1997, and by Franek for $t=6$ in 2002. Further tightenings $t=6,7$ and $8$ was recently obtained by Deza, Franek, and Liu.</p> <p>We investigate the computational framework used by Deza, Franek, and Liu. In particular, we present the benefits and limitations of different parallel computer memory architectures and parallel programming models. We propose a functional decomposition approach which is implemented in C++ with POSIX thread (Pthread) libraries for multi-threading. Computational benchmarking on the parallelized framework and a performance analysis including a comparison with the original computational framework are presented.</p> / Master of Science (MSc)

Ce travail de thèse concerne la fouille de données sur des graphes attribués. Il s'agit de graphes dans lesquels des propriétés, encodées sous forme d'attributs, sont associées à chaque sommet. Notre objectif est la découverte, dans ce type de données, de sous-graphes organisés en plusieurs groupes de sommets fortement connectés et homogènes au regard des attributs. Plus précisément, nous définissons l'extraction sous contraintes d'ensembles de sous-graphes densément connectés et tels que les sommets partagent suffisamment d'attributs. Pour cela nous proposons deux familles de motifs originales ainsi que les algorithmes justes et complets permettant leur extraction efficace sous contraintes. La première famille, nommée Ensembles Maximaux de Cliques Homogènes, correspond à des motifs satisfaisant des contraintes concernant le nombre de sous-graphes denses, la taille de ces sous-graphes et le nombre d'attributs partagés. La seconde famille, nommée Collections Homogènes de k-cliques Percolées emploie quant à elle une notion de densité plus relaxée permettant d'adapter la méthode aux données avec des valeurs manquantes. Ces deux méthodes sont appliquées à l'analyse de deux types de réseaux, les réseaux de coopérations entre chercheurs et les réseaux d'interactions de protéines. Les motifs obtenus mettent en évidence des structures utiles dans un processus de prise de décision. Ainsi, dans un réseau de coopérations entre chercheurs, l'analyse de ces structures peut aider à la mise en place de collaborations scientifiques entre des groupes travaillant sur un même domaine. Dans le contexte d'un graphe de protéines, les structures exhibées permettent d'étudier les relations entre des modules de protéines intervenant dans des situations biologiques similaires. L'étude des performances en fonction de différentes caractéristiques de graphes attribués réels et synthétiques montre que les approches proposées sont utilisables sur de grands jeux de données.

<p>Doktorska disertacija se bavi temama rešavanja računarski teških<br />problema kombinatorne optimizacije. Istaknut je problem maksimalne<br />klike kao predstavnik određenih struktura u grafovima. Problem<br />maksimalne klike i sa njim povezani problemi su formulisani kao<br />nelinearne funkcije. Rešavani su sa ciljem otkrivanja novih metoda<br />koje pronalaze dobre aproksimacije rešenja za neko razumno vreme.<br />Predložene su varijante Metode promenljivih okolina na rešavanje<br />maksimalne klike u grafu. Povezani problemi na grafovima se mogu<br />primeniti na pretragu informacija, raspoređivanje, procesiranje<br />signala, teoriju klasifikacije, teoriju kodiranja, itd. Svi algoritmi<br />su implementirani i uspešno testirani na brojnim različitim<br />primerima.</p> / <p>This Ph.D. thesis addresses topics NP hard problem solving approaches in<br />combinatorial optimization and according to that it is highlighted maximum<br />clique problem as a representative of certain structures in graphs. Maximum<br />clique problem and related problems with this have been formulated as non<br />linear functions which have been solved to research for new methods and<br />good solution approximations for some reasonable time. It has been<br />proposed several different extensions of Variable Neighborhood Search<br />method. Related problems on graphs could be applied on information<br />retrieval, scheduling, signal processing, theory of classi_cation, theory of<br />coding, etc. Algorithms are implemented and successfully tested on various<br />different tasks.</p>

Les réseaux de capteurs corporels représentent un enjeu sociétal important en permettant des soins de meilleure qualité avec un coût réduit. Ces derniers sont utilisés pour détecter des anomalies dès leur apparition et ainsi intervenir au plus vite. Les capteurs sont soumis à de nombreuses contraintes de fiabilité, robustesse, taille et consommation. Dans cette thèse, les différentes opérations réalisées par les réseaux de capteurs corporels sont analysées. La consommation de chacune d'elles est évaluée afin de guider les axes de recherche pour améliorer l'autonomie énergétique des capteurs. Un capteur pour la détection d'arythmie sur des signaux cardiaques est proposé. Il intègre un traitement du signal via l'utilisation d'un réseau de neurone à cliques. Le système proposé est simulé et offre une exactitude de classification de 95 % pour la détection de trois types d'arythmie. Le prototypage du système via la fabrication d'un circuit mixte analogique/numérique en CMOS 65 nm montre une consommation du capteur de l'ordre de 1,4 μJ. Pour réduire encore plus l'énergie, une nouvelle méthode d'acquisition est utilisée. Une architecture de convertisseur est proposée pour l'acquisition et le traitement de signaux cardiaques. Cette dernière laisse espérer une consommation de l'ordre de 1,18 nJ pour acquérir les paramètres tout en offrant une exactitude de classification proche de 98 %. Cette étude permet d'ouvrir la voie vers la mise en place de capteurs très basse consommation pouvant durer toute une vie avec une simple pile. / Body area sensor networks gained great focused through the promiseof better quality and cheaper medical care system. They are used todetect anomalies and treat them as soon as they arise. Sensors are under heavy constraints such as reliability, sturdiness, size and power consumption. This thesis analyzes the operations perform by a body area sensor network. The different energy requirements are evaluated in order to choose the focus of the research to improve the battery life of the sensors. A sensor for arrhythmia detection is proposed. It includes some signal processing through a clique-based neural network. The system simulations allow a classification between three types of arrhythmia with 95 % accuracy. The prototype, based on a 65 nm CMOS mixed signal circuit, requires only 1.4 μJ. To further reduce energy consumption, a new sensing method is used. A converter architecture is proposed for heart beat acquisition. Simulations and estimation show a 1.18 nJ energy requirement for parameter acquisition while offering 98 % classification accuracy. This work leads the way to the development of low energy sensor with a lifetime battery life.

Interval graphs, intersection graphs of segments on a real line (intervals), play a key role in the study of algorithms and special structural properties. Unit interval graphs, their proper subclass, where each interval has a unit length, has also been extensively studied. We study mixed unit interval graphs-a generalization of unit interval graphs where each interval has still a unit length, but intervals of more than one type (open, closed, semi-closed) are allowed. This small modification captures a much richer class of graphs. In particular, mixed unit interval graphs are not claw-free, compared to unit interval graphs. Heggernes, Meister, and Papadopoulos defined a representation of unit interval graphs called the bubble model which turned out to be useful in algorithm design. We extend this model to the class of mixed unit interval graphs. The original bubble model was used by Boyaci, Ekim, and Shalom for proving the polynomiality of the MaxCut problem on unit interval graphs. However, we found a significant mistake in the proof which seems to be hardly repairable. Moreover, we demonstrate advantages of such model by providing a subexponential-time algorithm solving the MaxCut problem on mixed unit interval graphs using our extended version of the bubble model. In addition, it gives us a polynomial-time...

本篇論文旨在探討三民主義青年團與中國國民黨衝突的結構性原因，及其在1949年國民黨政權潰敗過程裡所起的作用。除緒論與結論外，共計五章。大要如下: 第一章: 國民黨派系對峙的延續。本章對三青團成立背景與權力結構的分析，將有助於從派系政治面考察黨團關係自始即欠缺穩定的原因。 第二章: 雙軌競進的黨團體制。從新舊意識分明與體制分劃不清的角度出發，發展出具體的歷史敘事，從而導入黨團關係失衡的論證當中。 第三章: 革新聲中的派系權謀政治。以三青團與國民黨的兩次全國代表大會及開展於抗戰前後的革新運動為例，說明三青團與黨內各派系之間的政治操作與利益分配。 第四章: 三青團二全大會的組黨風潮。以1946年團二全大會為例，說明三青團欲將多年來渾沌的黨團關係做一徹底解決的努力，兼及全會閉幕後嶄新的權力格局。 第五章: 黨團統一與黨權鬆落。旨就蔣介石解決黨團摩擦的決心進行歷史分析，並對黨團統一的辦法與其後原黨團雙方仍分軫域的實情多所著墨。 本章將與前述章節產生相互辯證的效果，以便說明黨團關係在國民黨退出中國大陸的過程中所起的作用，和1950年蔣介石在台灣實施黨務改造的歷史背景。

Tous les problèmes définissables en \emph{logique monadique du second ordre } peuvent être résolus en temps polynomial dans les classes de graphes qui ont une \emph{largeur de clique} bornée. La largeur de clique est un paramètre de graphe défini de manière algébrique, c'est-à-dire, à partir d'opérations de composition de graphes. La \emph{largeur de rang}, définie de manière combinatoire, est une notion équivalente à la largeur de clique des graphes non orientés. Nous donnons une caractérisation algébrique de la largeur de rang et nous montrons qu'elle est linéairement bornée par la largeur arborescente. Nous proposons également une notion de largeur de rang pour les graphes orientés et une relation de \emph{vertex-minor} pour les graphes orientés. Nous montrons que les graphes orientés qui ont une largeur de rang bornée sont caractérisés par une liste finie de graphes orientés à exclure.<br>Beaucoup de classes de graphes n'ont pas une largeur de rang bornée, par exemple, les graphes planaires. Nous nous intéressons aux systèmes d'étiquetage dans ces classes de graphes. Un système d'étiquetage pour une propriété $P$ dans un graphe $G$, consiste à assigner une étiquette, aussi petite que possible, à chaque sommet de telle sorte que l'on puisse vérifier si $G$ satisfait $P$ en n'utilisant que les étiquettes des sommets. Nous montrons que si $P$ est une propriété définissable en \emph{logique du premier ordre} alors, certaines classes de graphes de \emph{largeur de clique localement bornée} admettent un système d'étiquetage pour $P$ avec des étiquettes de taille logarithmique. Parmi ces classes on peut citer les classes de graphes de degré borné, les graphes planaires et plus généralement les classes de graphes qui excluent un apex comme mineur et, les graphes d'intervalle unitaire.<br>Si $x$ et $y$ sont deux sommets, $X$ un ensemble de sommets et $F$ un ensemble d'arêtes, nous notons $Conn(x,y,X,F)$ la propriété qui vérifie dans un graphe donné si $x$ et $y$ sont connectés par un chemin, qui ne passe par aucun sommet de $X$ ni aucune arête de $F$. Cette propriété n'est pas définissable en logique du premier ordre. Nous montrons qu'elle admet un système d'étiquetage avec des étiquettes de taille logarithmique dans les graphes planaires. Nous montrons enfin que $Conn(x,y,X,\emptyset)$ admet également un système d'étiquetage avec des étiquettes de taille logarithmique dans des classes de graphes qui sont définies comme des \emph{combinaisons} de graphes qui ont une petite largeur de clique et telle que le graphe d'intersection de ces derniers est planaire et est de degré borné.

Abstract Results of analyses conducted on data collected from 313 employees of one University. The results of this research indicate as follows: Dimensionality of Organizational Politics Perceptions The responses to the 32-items Perceptions of Organizational Politics Scale (POPS) were subjected to principal components analysis with Varimax rotation. A four-factor solution was found to be most interpretable, with loadings of .50 and above used as an item retention criterion, resulting in a total of 16 items being retained across the four tactical importances. It is comprised four subscales: (1) Supervisor Behavior, (2) General Politics Behavior, (3) Organization Policies and Practices, and (4) Coworker & Clique Behavior. Relationships between Demographic Variables and Perceptions of Organizational Politics 1. Female¡¦s ¡§Supervisor Behavior¡¨ consciousness is stronger than male, and male¡¦s ¡§Coworker & Clique Behavior¡¨ consciousness is greater than female. 2. Subordinate¡¦s ¡§Organization Policies and Practices¡¨ consciousness is stronger than executives or above. 3. Regular staff members¡¦ ¡§Coworker & Clique Behavior¡¨ consciousness is much than non-regular staff members. 4. The University public servants¡¦ ¡§Supervisor Behavior¡¨ consciousness is much stronger than instructors. 5. Bachelor¡¦s level of education¡¦s ¡§Organization Policies and Practices¡¨ consciousness is greater than Mater¡¦s level of education or above. Relationships between Perceptions of Organizational Politics and Organizational Commitment 1. Organizational Politics was negatively related absolutely to¡¨ Retention Commitment¡¨. 2. Organizational Politics was negatively related partly to ¡§Value Commitment¡¨. 3. Organizational Politics was negatively related t partly to ¡§Effort Commitment¡¨. Control some Demographic Variables, reported special relationships 1. Reported positively correlations between ¡§Supervisor Behavior¡¨ and ¡§Value Commitment¡¨ with executives or above. 2. Reported positively correlations between¡¨ General Politics Behavior¡¨ and ¡¨ Effort Commitment¡¨ with female employees, subordinates and non-regular staff figures. Key word: Perceptions of Organizational Politics, Supervisor Behavior, General Politics Behavior, Organization Policies and Practices, Coworker & Clique Behavior, Organizational Commitment, Retention Commitment, Value Commitment, Effort Commitment.