169,791 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
A greedy approach to compute a minimum cycle basis of a directed graph
No full textGiven a directed graph D = (V, A), we consider its cycle space C[D] , i.e. the vector subspace of Q|A| spanned by the incidence vectors of the oriented cycles of D. An oriented cycle of D is just any cycle of the underlying undirected graph of D along with an orientation; its incidence vector is 0 on the arcs not included, while, for the included arcs, it is +1 on the arcs oriented according to the orientation and −1 on the arcs going backward.
Assume a nonnegative weight w_a ∈ R+ is associated to each arc a of D. We can extend the weighting w to subsets F of A and to families F
of such subsets by defining w(F ) := f ∈F w(f ) and w(F) := F ∈F w(F ). Given
the pair (D, w), we are interested in computing a minimum weight basis of C[D].
This problem is strongly related to the classical problem of computing a minimum
cycle basis of an undirected graph. In 1987, Horton developed the first polynomial
time algorithm for computing a minimum cycle basis of an undirected graph. As for
directed graphs, the first algorithm for computing a minimum directed cycle basis
is due to Kavitha and Mehlhorn. Its asymptotic complexity is O(m^4 n).
In this paper, we show how the original approach of Horton can be actually pur-
sued also in the context of directed graphs, while retaining its simplicity. This both
allows for a practical O(m^4 n) adaptation of Horton’s original algorithm requiring
only minor modifications in the actual code and for a more involved O(m^{ω+1} n)
solution. At the end, we discuss the applicability of this approach to more spe-
cialized classes of directed cycle bases, namely, integral cycle bases and generalized fundamental cycle bases
New length bounds for cycle bases
No full textBased 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
Primaer 1
No full textAs the opening T of C shows, this book's 202 pages split near the middle. After a short inroduction the first half of the book presents texts, organized into these groups: Parabeln, Epische Fabeln, Gleichnisse, Rhetorische Fabeln, Rhetorische Fabelketten, and Epigramme. In the second half of the book, Liebchen presents his criteria for these categories. Here he presents three principles of the fable, and then in several sections shows the errors and confusions he believes people get into by not using these principles. In the introduction, Liebchen points out that fables give pleasure, that fables introduce the Aha! moment, that adults do not feel themselves addressed by fable today and that people are confused about exactly what fable is. We need, then, to attend to the form of fable. My question about Liebchen's good fable texts is: Did he create them all? In the second half of the book, before offering his three principles of fables, Liebchen disagrees with the oft-stated theory that fables are indirect, self-protective speech. Fabulists suffer for what they say/write. Here are the three principles: First is das Prinzip des Mittels: fables' actors are lower creatures. Their characters are already known: So fable depends on three Verfremdungseffekte: 1.The effect of quick characterization. Brevity is important: fable makes a complex case comprehensible. 2. The second effect is reduction of feelings by creating a distance between us and the characters. We are not taken with pity and fear over the characters; we rather understand the consequences they have prepared for themselves. We have the feeling of being superior to them. 3. Everyday stuff is pushed into the realm of the special (des Besonderen). So we get unusual characters in an unusual place dealing with our everyday issues. Second is das Prinzip des Zweck, which is Verstehen. A good example is Liebchen's fable about good advice. A clever fox gives a naïve dog this advice: Never accept advice. Now, should the dog accept that advice? Third is das Prinzip des Ziels, which is Erkenntnis, in deren Folgschaft ein verändertes Verhalten steht. Fable goes beyond simile in wanting not just understanding but also a change in behavior. Fable changes nothing, but for one who is willing to think, it can help change. Fable has suffered through its misuse for moral doctrine. Simile does not have the Ziel of either fable or parable. It is not there to change behavior. Parable uses only one of the three Effekts: des besonderen. It does not try to create distance by using animals or try to create a sense of superiority. Liebchen uses The Prodigal Son as a favorite example of parable. The book uses four illustrations from various sources, listed on 201.Erste AuflageWilfried Liebche
Benchmarks for Strictly Fundamental Cycle Bases
No full textIn 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
Computing delay resistant railway timetables
No full textIn the past, much research has been dedicated to compute optimum railway timetables. A typical objective has been the minimization of passenger waiting times. But only the planned nominal waiting times have been addressed, whereas delays as they occur in daily operations have been neglected. Delays have been rather treated mainly in an online context and solved as a separate optimization problem, called delay management. We provide the first computational study which aims at computing delay resistant periodic timetables. In particular we assess the delay resistance of a timetable by evaluating it subject to several delay scenarios to which optimum delay management will be applied. We arrive at computing delay resistant timetables by selecting a new objective function which we design to be somehow in the middle of the traditional simple timetabling objective and the sophisticated delay management objective. This is a slight extension of the concept of "light robustness" (LR) as it has been proposed by Fischetti and Monaci [2006. Robust optimization through branch-and-price. In: Proceedings of AIRO]. Moreover, in our application we are able to provide accurate interpretations for the ingredients of LR. We apply this new technique to real-world data of a part of the German railway network of Deutsche Bahn AG. Our computational results suggest that a significant decrease of passenger delays can be obtained at a relatively small price of robustness, i.e. by increasing the nominal travel times of the passengers. (C) 2009 Elsevier Ltd. All rights reserved
Going Beyond Counting First Authors in Author Co-citation Analysis
No full textThe 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
Cycle bases in graphs characterization, algorithms, complexity, and applications.
No full textCycles in graphs play an important role in many applications, e.g., analysis of electrical networks, analysis of chemical and biological pathways, periodic scheduling, and graph drawing. From a mathematical point of view, cycles in graphs have a rich structure. Cycle bases are a compact description of the set of all cycles of a graph. In this paper, we survey the state of knowledge on cycle bases and also derive some new results. We introduce different kinds of cycle bases, characterize them in terms of their cycle matrix, and prove structural results and apriori length bounds. We provide polynomial algorithms for the minimum cycle basis problem for some of the classes and prove APX -hardness for others.
We also discuss three applications and show that they require different kinds of cycle bases
Mitomycin C in highly myopic eyes - Author reply
No full textOphthalmology. 2005 Feb;112(2):208-18; discussion 219.
Mitomycin C modulation of corneal wound healing after photorefractive keratectomy in highly myopic eyes.
Gambato C, Ghirlando A, Moretto E, Busato F, Midena E.
SourceRefractive Surgery Service and Antimetabolite Therapy Research Unit, Department of Ophthalmology, University of Padova, Padova, Italy.
Abstract
PURPOSE: To evaluate the role of topical mitomycin C in corneal wound healing (CWH) after photorefractive keratectomy (PRK) in highly myopic eyes.
DESIGN: Prospective, double-masked, randomized clinical trial.
PARTICIPANTS: Seventy-two eyes of 36 patients affected by high (>7 diopters) myopia.
METHODS: In each patient, one eye was randomly assigned to PRK with intraoperative topical 0.02% mitomycin C application, and the fellow eye was treated with a placebo. Postoperatively, mitomycin C-treated eyes received artificial tears (3 times daily, tapered in 3 months), whereas the fellow eye was treated with fluorometholone sodium 2% and artificial tears (3 times daily, tapered in 3 months).
MAIN OUTCOME MEASURES: Uncorrected visual acuity (UCVA) and best-corrected visual acuity (BCVA), contrast sensitivity, manifest refraction, and biomicroscopy. Contrast sensitivity was determined using the Pelli-Robson chart. Corneal confocal microscopy documented CWH.
RESULTS: Mean follow-up was 18 months (range, 12-36). No side effects or toxic effects were documented. At 12-month follow-up examination, UCVAs (logarithm of the minimum angle of resolution) were 0.4+/-0.48 and 0.5+/-0.53 (P = .03) in mitomycin C-treated eyes and corticosteroid-treated eyes, respectively. At 1 year, corneal haze developed in 20% of corticosteroid-treated eyes, versus 0% of mitomycin C-treated eyes. At 12, 24, and 36 months, corneal confocal microscopy showed activated keratocytes and extracellular matrix significantly more evident in untreated eyes (Ps = 0.004, 0.024, and 0.046, respectively).
CONCLUSION: Topical intraoperative application of 0.02% mitomycin C can reduce haze formation in highly myopic eyes undergoing PRK.
Comment in
Ophthalmology. 2006 Feb;113(2):357; author reply 357-8
- …
