100,930 research outputs found
On the Parameterized Complexity of Contraction to Generalization of Trees
No full textFor a family of graphs F, the F-Contraction problem takes as an input a graph G and an integer k, and the goal is to decide if there exists S \subseteq E(G) of size at most k such that G/S belongs to F. Here, G/S is the graph obtained from G by contracting all the edges in S. Heggernes et al.[Algorithmica (2014)] were the first to study edge contraction problems in the realm of Parameterized Complexity. They studied \cal F-Contraction when F is a simple family of graphs such as trees and paths. In this paper, we study the F-Contraction problem, where F generalizes the family of trees. In particular, we define this generalization in a "parameterized way". Let T_\ell be the family of graphs such that each graph in T_\ell can be made into a tree by deleting at most \ell edges. Thus, the problem we study is T_\ell-Contraction. We design an FPT algorithm for T_\ell-Contraction running in time O((\ncol)^{O(k + \ell)} * n^{O(1)}). Furthermore, we show that the problem does not admit a polynomial kernel when parameterized by k. Inspired by the negative result for the kernelization, we design a lossy kernel for T_\ell-Contraction of size O([k(k + 2\ell)] ^{(\lceil {\frac{\alpha}{\alpha-1}\rceil + 1)}})
On the Parameterized Complexity of Grid Contraction
No full textFor a family of graphs , the -Contraction problem takes as an input a graph G and an integer k, and the goal is to decide if there exists F ⊆ E(G) of size at most k such that G/F belongs to . Here, G/F is the graph obtained from G by contracting all the edges in F. In this article, we initiate the study of Grid Contraction from the parameterized complexity point of view. We present a fixed parameter tractable algorithm, running in time c^k ⋅ |V(G)|^{{O}(1)}, for this problem. We complement this result by proving that unless ETH fails, there is no algorithm for Grid Contraction with running time c^{o(k)} ⋅ |V(G)|^{{O}(1)}. We also present a polynomial kernel for this problem
“O, she’s warm!”: The taking of hands … and bears … and time’s … in The Winter’s Tale
No full textShakespeare wrote words and plays. Words might well be considered to be the ‘life blood’ of a play. But plays are more than words. Plays have characters, movement, costumes and props. Words inhabit and animate, give rhyme and reason to an actor being on a stage, performing for an audience. But between the words, the play still exists. This thesis is an exploration of those ‘moments’ that are played out in silence and are watched rather than heard. To tell the story of The Winter’s Tale, Shakespeare was faced with some specific problems. There are essentially two tales to be told in the space of one play. The first requires for an all consuming jealousy to be played out. He solved this with a simple and understandable wordless action. Then to conclude this first tragic section, the story demanded that a helpless baby be abandoned - lost. Here he used an old trick in a new and surprising way, to be played quickly and, with his unerring sense of staging, for a laugh. The second tale then had to begin, and the baby had to become a woman. For this he used a convention - unconventionally. Finally, at the end of the play, he decided to change the story. To conclude his tale, the tale he was telling, with an image of redemption, reconciliation and hope. Of all the moments, this is the one that is the quietest, slowest and most beautifully painted. This thesis is an exploration of those moments. A discussion about how Shakespeare, who has probably added more words into the lexicon that any other person, was also essentially a visual artist. That he ‘drew and painted and sculpted’ - creating stage pictures
The Hasidic Tale
No full textStory-telling has been an integral part of the hasidic movement from its inception. Stories about the hasidic leaders and their mystical powers attracted followers and maintained their devotion, and still do so today. This important work, based on analysis of all the published anthologies of such stories, presents them by theme and traces their origins. Originally published in Hebrew and expanded for this edition, it makes a fascinating contribution to the history of hasidism, of Hebrew literature, and of Jewish popular culture.Cover -- Contents -- Note on Transliteration, Translation, and Names -- Introduction -- 1. The Hasidic Tale as Perceived by Hasidim -- 2. The Tsadik, his Followers, and his Opponents -- 3. Matchmaking and Marriages -- 4. The Blessing of Children: Birth and Offspring -- 5. Agunot -- 6. A Life of Sin -- 7. Illness and Physicians -- 8. The Dead, Burial, and the World to Come -- 9. Transmigration of the Soul and Dybbuks -- 10. The Powers of Evil and the War against Them -- 11. Apostasy and Apostates -- 12. Ritual Slaughterers -- 13. The Tamim: The Simple Person -- 14. Hidden Tsadikim -- 15. Hospitality -- 16. The Prophet Elijah -- 17. The Ba'al Shem Tov's Unsuccessful Pilgrimage to the Land of Israel -- Appendix: Supplementary Notes -- Glossary -- A -- B -- C -- D -- E -- G -- H -- I -- K -- L -- M -- N -- P -- R -- S -- T -- U -- V -- W -- Y -- Z -- Gazetteer of Place Names in Central and Eastern Europe -- Bibliography -- Index -- A -- B -- C -- D -- E -- F -- G -- H -- I -- J -- K -- L -- M -- N -- O -- P -- R -- S -- T -- U -- V -- W -- Y -- ZStory-telling has been an integral part of the hasidic movement from its inception. Stories about the hasidic leaders and their mystical powers attracted followers and maintained their devotion, and still do so today. This important work, based on analysis of all the published anthologies of such stories, presents them by theme and traces their origins. Originally published in Hebrew and expanded for this edition, it makes a fascinating contribution to the history of hasidism, of Hebrew literature, and of Jewish popular culture.Description based on publisher supplied metadata and other sources.Electronic reproduction. Ann Arbor, Michigan : ProQuest Ebook Central, YYYY. Available via World Wide Web. Access may be limited to ProQuest Ebook Central affiliated libraries
Assessing the George W. Bush Presidency: A Tale of Two Terms
No full textIn one of the first volumes assessing the full two terms of the George W. Bush presidency, Wroe and Herbert have gathered the work of leading American and European scholars. In fifteen succinct and incisive chapters, authorities such as Jim Pfiffner, John Maltese, Graham Wilson and Alan Gitelson offer assessments of the Bush administration's successes and failures. Extensive attention is paid to Bush's foreign policy, including 'The War on Terror' but the focus is broadened to absorb not only the Bush Doctrine and its repercussions, but also his trade and homeland security policies. The president's domestic leadership in economics and social policy is investigated, as are his dealings as president with the other institutions of the U.S. political system. The result is a comprehensive guide to the Bush presidency and its legacy
On the Parameterized Approximability of Contraction to Classes of Chordal Graphs
No full textA graph operation that contracts edges is one of the fundamental operations in the theory of graph minors. Parameterized Complexity of editing to a family of graphs by contracting k edges has recently gained substantial scientific attention, and several new results have been obtained. Some important families of graphs, namely the subfamilies of chordal graphs, in the context of edge contractions, have proven to be significantly difficult than one might expect. In this paper, we study the F-Contraction problem, where F is a subfamily of chordal graphs, in the realm of parameterized approximation. Formally, given a graph G and an integer k, F-Contraction asks whether there exists X ⊆ E(G) such that G/X ∈ F and |X| ≤ k. Here, G/X is the graph obtained from G by contracting edges in X. We obtain the following results for the F-Contraction problem.
- Clique Contraction is known to be FPT. However, unless NP ⊆ coNP/poly, it does not admit a polynomial kernel. We show that it admits a polynomial-size approximate kernelization scheme (PSAKS). That is, it admits a (1 + ε)-approximate kernel with {O}(k^{f(ε)}) vertices for every ε > 0.
- Split Contraction is known to be W[1]-Hard. We deconstruct this intractability result in two ways. Firstly, we give a (2+ε)-approximate polynomial kernel for Split Contraction (which also implies a factor (2+ε)-FPT-approximation algorithm for Split Contraction). Furthermore, we show that, assuming Gap-ETH, there is no (5/4-δ)-FPT-approximation algorithm for Split Contraction. Here, ε, δ > 0 are fixed constants.
- Chordal Contraction is known to be W[2]-Hard. We complement this result by observing that the existing W[2]-hardness reduction can be adapted to show that, assuming FPT ≠ W[1], there is no F(k)-FPT-approximation algorithm for Chordal Contraction. Here, F(k) is an arbitrary function depending on k alone. We say that an algorithm is an h(k)-FPT-approximation algorithm for the F-Contraction problem, if it runs in FPT time, and on any input (G, k) such that there exists X ⊆ E(G) satisfying G/X ∈ F and |X| ≤ k, it outputs an edge set Y of size at most h(k) ⋅ k for which G/Y is in F. We find it extremely interesting that three closely related problems have different behavior with respect to FPT-approximation
Variations on the Author
No full text“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
[Newspaper Clipping: Author Claims Evidence of Second JFK Assassin #1]
No full textNewspaper article titled "Author Claims Evidence of Second JFK Assassin." The article states that author Richard J. Whalen concluded "that there is circumstantial evidence to support the theory of a second assassin in the shooting of President John F. Kennedy.
Path Contraction Faster Than 2^n
No full textA graph G is contractible to a graph H if there is a set X subseteq E(G), such that G/X is isomorphic to H. Here, G/X is the graph obtained from G by contracting all the edges in X. For a family of graphs F, the F-Contraction problem takes as input a graph G on n vertices, and the objective is to output the largest integer t, such that G is contractible to a graph H in F, where |V(H)|=t. When F is the family of paths, then the corresponding F-Contraction problem is called Path Contraction. The problem Path Contraction admits a simple algorithm running in time 2^n * n^{O(1)}. In spite of the deceptive simplicity of the problem, beating the 2^n * n^{O(1)} bound for Path Contraction seems quite challenging. In this paper, we design an exact exponential time algorithm for Path Contraction that runs in time 1.99987^n * n^{O(1)}. We also define a problem called 3-Disjoint Connected Subgraphs, and design an algorithm for it that runs in time 1.88^n * n^{O(1)}. The above algorithm is used as a sub-routine in our algorithm for Path Contraction
- …
