7,188 research outputs found
Fixed-Parameter Tractability of the Weighted Edge Clique Partition Problem
No full textWe develop an FPT algorithm and a compression for the Weighted Edge Clique Partition (WECP) problem, where a graph with n vertices and integer edge weights is given together with an integer k, and the aim is to find k cliques, such that every edge appears in exactly as many cliques as its weight. The problem has been previously only studied in the unweighted version called Edge Clique Partition (ECP), where the edges need to be partitioned into k cliques. It was shown that ECP admits a kernel with k² vertices [Mujuni and Rosamond, 2008], but this kernel does not extend to WECP. The previously fastest algorithm known for ECP has a runtime of 2^(k²)n^O(1) [Issac, 2019]. For WECP we develop a compression (to a slightly more general problem) with 4^k vertices, and an algorithm with runtime 2^(k^(3/2)w^(1/2)log(k/w))n^O(1), where w is the maximum edge weight. The latter in particular improves the runtime for ECP to 2^(k^(3/2)log k)n^O(1)
The Author: Kent Davis
No full textKent Davis is a Montana based author of “A Riddle in Ruby” and the soon to be released sequel, “The Changer’s Key”
Author inscription in The Chinese slave-girl: a story of woman's life in China
No full textThis edition includes a gift inscription by author Rev. J.A. Davis, "To Rev. A. G. Russell with the warmest regards of the author J.A. Davis."Davis, John Agnell, 1839-1897
H. P. Davis Correspondence
No full textEntries include a handwritten letter from Davis suggesting that the Maine Author Collection could include works by the Davis family and the author Patten and typed letters of correspondence from the Maine State Library
Spanning Tree Congestion and Computation of Generalized Györi-Lovász Partition
No full textWe study a natural problem in graph sparsification, the Spanning Tree Congestion (STC) problem. Informally, it seeks a spanning tree with no tree-edge routing too many of the original edges.
For any general connected graph with n vertices and m edges, we show that its STC is at most O(sqrt{mn}), which is asymptotically optimal since we also demonstrate graphs with STC at least Omega(sqrt{mn}). We present a polynomial-time algorithm which computes a spanning tree with congestion O(sqrt{mn}* log n). We also present another algorithm for computing a spanning tree with congestion O(sqrt{mn}); this algorithm runs in sub-exponential time when m = omega(n log^2 n).
For achieving the above results, an important intermediate theorem is generalized Györi-Lovász theorem. Chen et al. [Jiangzhuo Chen et al., 2007] gave a non-constructive proof. We give the first elementary and constructive proof with a local search algorithm of running time O^*(4^n). We discuss some consequences of the theorem concerning graph partitioning, which might be of independent interest.
We also show that for any graph which satisfies certain expanding properties, its STC is at most O(n), and a corresponding spanning tree can be computed in polynomial time. We then use this to show that a random graph has STC Theta(n) with high probability
On the Parameterized Complexity of Biclique Cover and Partition
No full textGiven a bipartite graph G, we consider the decision problem called BicliqueCover for a fixed positive integer parameter k where we are asked whether the edges of G can be covered with at most k complete bipartite subgraphs (a.k.a. bicliques). In the BicliquePartition problem, we have the additional constraint that each edge should appear in exactly one of the k bicliques. These problems are both known to be NP-complete but fixed parameter tractable. However, the known FPT algorithms have a running time that is doubly exponential in k, and the best known kernel for both problems is exponential in k. We build on this kernel and improve the running time for BicliquePartition to O*(2^{2k^2+k*log(k)+k}) by exploiting a linear algebraic view on this problem. On the other hand, we show that no such improvement is possible for BicliqueCover unless the Exponential Time Hypothesis (ETH) is false by proving a doubly exponential lower bound on the running time. We achieve this by giving a reduction from 3SAT on n variables to an instance of BicliqueCover with k=O(log(n)). As a further consequence of this reduction, we show that there is no subexponential kernel for BicliqueCover unless P=NP. Finally, we point out the significance of the exponential kernel mentioned above for the design of polynomial-time approximation algorithms for the optimization versions of both problems. That is, we show that it is possible to obtain approximation factors of n/log(n) for both problems, whereas the previous best approximation factor was n/sqrt(log(n))
Translation and response between Maurice Blanchot and Lydia Davis
No full textWhen an author translates a text by another writer, this translation is one form of a response to that text. Other responses may appear in their own writings that are more inflected with their authorial persona. Lydia Davis translated six books by Maurice Blanchot, including fiction and theoretical writings. Blanchot’s concept of the récit privileges non-conventional forms of narrative and it can be considered to have influenced Davis, a view shared in critical writing about Davis. However, responses to his fiction can also be found in Davis’s work. This article reads Lydia Davis’s story “Story” as a response to Maurice Blanchot’s récit, La Folie du jour, translated by Davis as “The Madness of the Day”. Both texts develop a narrative that questions the possibility of arriving at a single story: Blanchot’s narrator cannot tell the story of how he came to have glass ground into his eyes, while Davis’s narrator must try to understand a contradictory story told to her by her lover. However, Davis responds to Blanchot by reversing the perspective in the story: where Blanchot’s narrator must and cannot create a story that explains his situation in a judicial/medical context, Davis’s narrator is struggling to understand her lover’s story which does not explain the situation that they find themselves in. Davis’s narrator is therefore motivated by an emotional need to find an acceptable story that is absent from Blanchot’s narrator. This difference in motivation is central to the difference between Davis’s and Blanchot’s approach, and complicates any reading of his influence on her because she responds to his text in her own
Illustrator's flat signature in The novels and stories of Richard Harding Davis
No full textThis edition includes the flat signature of Illustrator Charles Dana Gibson on the frontispiece in "Gallegher, and other stories"; and a second signature in "Soldiers of Fortune". This is a limited-edition, 256-copy run of "The novels and stories of Richard Harding Davis" [v. 4]. Richard Harding Davis, author, 1864-1916.--v.1. The bar sinister and other stories.--v.2. The exiles and other stories.--v.3. Gallegher and other stories.--v.4. Soldiers of fortune.--v.5. Captain Macklin: his memoirs.--v.6. Ranson's Folly.--v.7. The White mice.-- v.8. The Scarlet car.--v.9. The bar sinister.--v.10. The man who could not lose.--v.11. The red cross girl.--v.12. The lost road.
Davis, Richard Harding, 1864-1916
Joshua Davis: Author of Spare Parts
No full textCitation: K-State First (2016). Joshua Davis: Author of Spare Parts [Flier]. Manhattan, Kansas: K-State First.Flyer advertising Joshua Davis's author talk at Kansas State University
- …
