1,721,079 research outputs found
Exact exponential algorithms for solving graph problems summary
No full textDe nombreux problèmes algorithmiques sont « difficiles », dans le sens où on ne sait pas les résoudre en temps polynomial par rapport à la taille de l’entrée, soit parce qu’ils sont NP-difficiles, soit, pour certains problèmes d’énumération, à cause du nombre exponentiel d'objets à énumérer. Depuis une quinzaine d’années on trouve un intérêt grandissant dans la littérature pour la conception d'algorithmes exacts sophistiqués afin de les résoudre le plus efficacement possible. Dans le cadre de cette thèse, nous nous intéressons à la conception d'algorithmes exacts exponentiels autour de trois problèmes difficiles. Nous étudions tout d'abord le problème d'optimisation Ensemble Connexe Tropical pour lequel nous décrivons un algorithme afin de le résoudre en général, puis un algorithme de branchement plus rapide pour le résoudre sur les arbres, ce problème restant difficile même dans ce cas. Nous nous intéressons ensuite au problème d'énumération Ensembles Dominants Minimaux, pour lequel nous donnons des algorithmes résolvant ce problème dans les graphes splits, cobipartis, ainsi que dans les graphes d'intervalles. Nous déduisons des bornes supérieures sur le nombre d'ensembles dominants minimaux admis par de tels graphes. La dernière étude de cette thèse concerne le problème d'optimisation Domination Romaine Faible dans lequel, étant donné un graphe nous cherchons à construire une fonction de pondération selon certaines propriétés. Le problème est NP-difficile en général, mais nous donnons un algorithme glouton linéaire calculant une telle fonction pour les graphes d'intervalles.Many algorithmic problems are « hard », in the sense of we do not know how to solve them in polynomialtime, either because they are NP-hard, or, for some enumeration problems, because the number of objectsto be produced is exponential. During the last fifteen years there was a growing interest in the design of exact algorithms to solve such problems as efficiently as possible. In the context of this thesis, we focus on the design of exponential exact algorithms for three hard problems. First, we study the optimisation problem Tropical Connected Set for which we describe an algorithm to solve it in the general case, then a faster branch-and-reduce algorithm to solve it on trees; the problem remains difficult even in this case. Secondly we focus on the Minimal Dominating Sets enumeration problem, for which we give algorithms to solve it on split, cobipartite and intervals graphs. As a byproduct, we establish upper bounds on the number of minimal dominating sets in such graphs. The last focus of this thesis concerns the Weak Roman Domination optimisation problem for which, given a graph, the goal is to build a weight function under some properties. The problem is NP-hard in general, but we give a linear greedy algorithm which computes such a function on interval graphs
Going Beyond Counting First Authors in Author Co-citation Analysis
Get PDFThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Variations on the Author
Get PDF“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
Appropriate Similarity Measures for Author Cocitation Analysis
Get PDFWe provide a number of new insights into the methodological discussion about author cocitation analysis. We first argue that the use of the Pearson correlation for measuring the similarity between authors’ cocitation profiles is not very satisfactory. We then discuss what kind of similarity measures may be used as an alternative to the Pearson correlation. We consider three similarity measures in particular. One is the well-known cosine. The other two similarity measures have not been used before in the bibliometric literature. Finally, we show by means of an example that our findings have a high practical relevance.information science;Pearson correlation;cosine;similarity measure;author cocitation analysis
Excat exponential time algorithms for NP-hard problems : domination, variants and generalizations
No full textLes premiers algorithmes exacts exponentiels pour résoudre des problèmes NP-difficiles datent des années soixante. Ces dernières années ont vu un intérêt croissant pour la conception de tels algorithmes tout comme pour l'amélioration de la précision de l'analyse de leur temps d'exécution. Ils sont motivés par les larges applications de problèmes réputés difficiles et qui, sous l'hypothèse P 6= NP, n'admettent pas d'algorithme polynomial en calculant une solution exacte. Dans cette thèse on s'intéresse au problème classique de la domination dans un graphe. On étudie également plusieurs variantes et généralisations de ce problème fondamental. Nous proposons des algorithmes exponentiels pour déterminer un ensemble dominant de taille minimum sur les graphes c-denses, cordaux, 4-cordaux, faiblement cordaux, cercles et bipartis. Puis, nous étudions le problème de la clique dominante qui demande de trouver un ensemble dominant qui soit aussi une clique du graphe. Nous proposons un algorithme Brancher & Réduire qui détermine une clique dominante de taille minimum. L'analyse du temps d'exécution est réalisée en utilisant la technique Mesurer pour Conquérir. Nous donnons ensuite un algorithme général pour énumérer tous les ensembles ( %)-dominants d'un graphe en temps O(cn), avec c < 2, sous certaines conditions sur les ensembles et %, et établissons une borne supérieure combinatoire sur leur nombre. Finalement, nous nous intéressons à un problème de domination partielle et obtenons un algorithme pour le problème de la domination romaine. Grâce à un algorithme basé sur le paradigme de la Programmation Dynamique, nous proposons un algorithme pour le problème de la domination avec des puissances variablesThe first exact exponential-time algorithms solving NP-hard problems date back to the sixties. The last years have seen an increasing interest for designing such algorithms as well as analysing their running time. The existence of many applications of well known hard problems is one of the main motivations. Moreover, under the hypothesis P 6= NP, apolynomial time algorithm for these problems does not exist. In this thesis, we deal with the classical domination problem in graphs. We are also interested in some variants and generalizations of this fondamental problem. We give exponential-time algorithms for computing a minimum dominating set on c-dense graphs, chordal graphs, 4-chordal graphs, weakly chordal graphs, circle graphs and bipartite graphs. Then, we study the dominating clique problem requiring to find a minimum dominating set inducing a clique of the graph. We provide a Branch & Reduce algorithm computing a minimum dominating clique. The analysis of the running time is done by using the Measure and Conquer technique. Afterwards, we propose a general algorithm for enumerating all (%)-dominating sets of a graph in time O(cn), with c < 2, under some assumptions on the sets and %. Subsequently, we establish a combinatorial upper bound on the number of such sets in a graph. Finally, we consider a partial dominating set problem and we give an algorithm for solving the Roman domination problem. Using the dynamic programming paradigm, we obtain an algorithm for the domination problem with flexible power
Dispelling the Myths Behind First-author Citation Counts
Get PDFWe conducted a full-scale evaluative citation analysis study of scholars in the XML research field to explore just how different from each other author rankings resulting from different citation counting methods actually are, and to demonstrate the capability of emerging data and tools on the Web in supporting more realistic citation counting methods. Our results contest some common arguments for the continued
use of first-author citation counts in the evaluation of scholars, such as high correlations between author rankings by first-author citation counts and other citation
counting methods, and high costs of using more realistic citation counting methods that are not well-supported by the ISI databases. It is argued that increasingly available digital full text research papers make it possible for citation analysis studies to go beyond what the ISI databases have directly supported and to employ more
sophisticated methods
Algorithmes exponentiels pour l'étiquetage, la domination et l'ordonnancement
Get PDFThis manuscript of Habilitation à Diriger des Recherches enlights some results obtained since my PhD, I defended in 2007. The presented results have been mainly published in international conferences and journals. Exponential-time algorithms are given to solve various decision, optimization and enumeration problems. First, we are interested in solving the L(2,1)-labeling problem for which several algorithms are described (based on branching, divide-and-conquer and dynamic programming). Some combinatorial bounds are also established to analyze those algorithms. Then we solve domination-like problems. We develop algorithms to solve a generalization of the dominating set problem and we give algorithms to enumerate minimal dominating sets in some graph classes. As a consequence, the analysis of these algorithms implies combinatorial bounds. Finally, we extend our field of applications of moderately exponential-time algorithms to scheduling problems. By using dynamic programming paradigm and by extending the sort-and-search approach, we are able to solve a family of scheduling problems.Ce manuscrit d’Habilitation à Diriger des Recherches met en lumière quelques résultats obtenus depuis ma thèse de doctorat soutenue en 2007. Ces résultats ont été, pour l’essentiel, publiés dans des conférences et des journaux internationaux. Des algorithmes exponentiels sont donnés pour résoudre des problèmes de décision, d’optimisation et d’énumération. On s’intéresse tout d’abord au problème d’étiquetage L(2,1) d’un graphe, pour lequel différents algorithmes sont décrits (basés sur du branchement, le paradigme diviser-pour-régner, ou la programmation dynamique). Des bornes combinatoires, nécessaires à l’analyse de ces algorithmes, sont également établies. Dans un second temps, nous résolvons des problèmes autour de la domination. Nous développons des algorithmes pour résoudre une généralisation de la domination et nous donnons des algorithmes pour énumérer les ensembles dominants minimaux dans des classes de graphes. L’analyse de ces algorithmes implique des bornes combinatoires. Finalement, nous étendons notre champ d’applications de l’algorithmique modérément exponentielle à des problèmes d’ordonnancement. Par le développement d’approches de type programmation dynamique et la généralisation de la méthode trier-et-chercher, nous proposons la résolution de toute une famille de problèmes d’ordonnancement
Algorithmes exacts et exponentiels pour les problèmes NP-difficiles : domination, variantes et généralisations
No full textThe first exact exponential-time algorithms solving NP-hard problems date back to the sixties. The last years have seen an increasing interest for designing such algorithms as well as analysing their running time. The existence of many applications of well known hard problems is one of the main motivations. Moreover, under the hypothesis P 6= NP, apolynomial time algorithm for these problems does not exist. In this thesis, we deal with the classical domination problem in graphs. We are also interested in some variants and generalizations of this fondamental problem. We give exponential-time algorithms for computing a minimum dominating set on c-dense graphs, chordal graphs, 4-chordal graphs, weakly chordal graphs, circle graphs and bipartite graphs. Then, we study the dominating clique problem requiring to find a minimum dominating set inducing a clique of the graph. We provide a Branch & Reduce algorithm computing a minimum dominating clique. The analysis of the running time is done by using the Measure and Conquer technique. Afterwards, we propose a general algorithm for enumerating all (%)-dominating sets of a graph in time O(cn), with c < 2, under some assumptions on the sets and %. Subsequently, we establish a combinatorial upper bound on the number of such sets in a graph. Finally, we consider a partial dominating set problem and we give an algorithm for solving the Roman domination problem. Using the dynamic programming paradigm, we obtain an algorithm for the domination problem with flexible powersLes premiers algorithmes exacts exponentiels pour résoudre des problèmes NP-difficiles datent des années soixante. Ces dernières années ont vu un intérêt croissant pour la conception de tels algorithmes tout comme pour l'amélioration de la précision de l'analyse de leur temps d'exécution. Ils sont motivés par les larges applications de problèmes réputés difficiles et qui, sous l'hypothèse P 6= NP, n'admettent pas d'algorithme polynomial en calculant une solution exacte. Dans cette thèse on s'intéresse au problème classique de la domination dans un graphe. On étudie également plusieurs variantes et généralisations de ce problème fondamental. Nous proposons des algorithmes exponentiels pour déterminer un ensemble dominant de taille minimum sur les graphes c-denses, cordaux, 4-cordaux, faiblement cordaux, cercles et bipartis. Puis, nous étudions le problème de la clique dominante qui demande de trouver un ensemble dominant qui soit aussi une clique du graphe. Nous proposons un algorithme Brancher & Réduire qui détermine une clique dominante de taille minimum. L'analyse du temps d'exécution est réalisée en utilisant la technique Mesurer pour Conquérir. Nous donnons ensuite un algorithme général pour énumérer tous les ensembles ( %)-dominants d'un graphe en temps O(cn), avec c < 2, sous certaines conditions sur les ensembles et %, et établissons une borne supérieure combinatoire sur leur nombre. Finalement, nous nous intéressons à un problème de domination partielle et obtenons un algorithme pour le problème de la domination romaine. Grâce à un algorithme basé sur le paradigme de la Programmation Dynamique, nous proposons un algorithme pour le problème de la domination avec des puissances variable
- …
