1,720,964 research outputs found
Classes of cycle bases
No full textIn the last years, new variants of the minimum cycle basis (MCB) problem and new classes of cycle bases have been introduced,
as motivated by several applications from disparate areas of scientific and technological inquiries. At present, the complexity status
of the MCB problem has been settled only for undirected, directed, and strictly fundamental cycle bases.
In this paper, we offer an unitary classification accommodating these three classes and further including the following four relevant
classes: 2-bases (or planar bases), weakly fundamental cycle bases, totally unimodular cycle bases, and integral cycle bases. The
classification is complete in that, for each ordered pair (A, B) of classes considered, we either prove that A ⊆ B holds for every
graph or provide a counterexample graph for which A B. The seven notions of cycle bases are distinct (either A B or B A is
exhibited for each pair (A, B)).
All counterexamples proposed have been designed to be ultimately effective in separating the various algorithmic variants of the
MCB problem naturally associated to each one of these seven classes. Furthermore, we provide a linear time algorithm for computing
a minimum 2-basis of a graph. Finally, notice that the resolution of the complexity status of some of the remaining three classes
would have an immediate impact on practical applications, as for instance in periodic railway timetabling, only integral cycle bases
are of direct use
New length bounds for cycle bases
Full text linkBased on a recent work by Abraham, Bartal and Neiman (2007), we construct a strictly fundamental cycle basis of length 0(n(2)) for any unweighted graph, whence proving the conjecture of Deo et al. (1982). For weighted graphs, we construct cycle bases of length O(W - log n log log n), where W denotes the sum of the weights of the edges. This improves the upper bound that follows from the result of Elkin et al. (2005) by a logarithmic factor and, for comparison from below, some natural classes of large girth graphs are known to exhibit minimum cycle bases of length Q (W - log n). We achieve this bound for weighted graphs by not restricting ourselves to strictly fundamental cycle bases-as it is inherent to the approach of Elkin et al-but rather also considering weakly fundamental cycle bases in our construction. This way we profit from some nice properties of Hierarchically Well-Separated Trees that were introduced by Bartal (1998)
Lower bounds for strictly fundamental cycle bases in grid graphs.
No full textConsider the following problem: compute a spanning tree such that the sum of the lengths of its induced fundamental circuits is as small as possible. We motivate why planar square grid graphs are very relevant instances for this problem. In particular, other contributions already showed that the identification of strong lower bounds is highly challenging. Asymptotically, for a graph on n vertices, Alon et al. [SIAM J Comput 24(1995), 78–100] obtained a lower bound of Ω(n log n). We raise the n log n coefficient by a factor of 325. Concerning optimality proofs, the largest grid for which provably optimum solutions were known is 6 × 6, and it was obtained by massive MIP computing power. Here, we present a combinatorial optimality proof even for the 8 × 8 grid. These two results are complemented by new combinatorial lower bounds for the dimensions in which earlier empirical computations were performed, i.e., for up to 10,000 vertices
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe 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
Full text link“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
Full text linkWe 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
Dispelling the Myths Behind First-author Citation Counts
Full text linkWe 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
Benchmarks for Strictly Fundamental Cycle Bases
Full text linkIn the Minimum Strictly Fundamental Cycle Basis (MSFCB) problem one is looking for a spanning tree such that the sum of the lengths of its induced fundamental circuits is minimum.
We identify square planar grid graphs as being very challenging testbeds for the MSFCB. The best lower and upper bounds for this problem are due to Alon, Karp, Peleg, and West (1995) and to Amaldi et al. (2004).
We improve their bounds significantly, both empirically and asymptotically. Ideally, these new benchmarks will serve as a reference for the performance of any new heuristic for the MSFCB problem
- …
