2,335 research outputs found
Fractional Covers of Hypergraphs with Bounded Multi-Intersection
Get PDFFractional (hyper-)graph theory is concerned with the specific problems that
arise when fractional analogues of otherwise integer-valued (hyper-)graph
invariants are considered. The focus of this paper is on fractional edge covers
of hypergraphs. Our main technical result generalizes and unifies previous
conditions under which the size of the support of fractional edge covers is
bounded independently of the size of the hypergraph itself. This allows us to
extend previous tractability results for checking if the fractional hypertree
width of a given hypergraph is for some constant . We also show how
our results translate to fractional vertex covers
FPT Approximation of Generalised Hypertree Width for Bounded Intersection Hypergraphs
Get PDFGeneralised hypertree width (ghw) is a hypergraph parameter that is central to the tractability of many prominent problems with natural hypergraph structure. Computing ghw of a hypergraph is notoriously hard. The decision version of the problem, checking whether ghw(H) ≤ k, is paraNP-hard when parameterised by k. Furthermore, approximation of ghw is at least as hard as approximation of Set-Cover, which is known to not admit any FPT approximation algorithms.
Research in the computation of ghw so far has focused on identifying structural restrictions to hypergraphs - such as bounds on the size of edge intersections - that permit XP algorithms for ghw. Yet, even under these restrictions that problem has so far evaded any kind of FPT algorithm. In this paper we make the first step towards FPT algorithms for ghw by showing that the parameter can be approximated in FPT time for graphs of bounded edge intersection size. In concrete terms we show that there exists an FPT algorithm, parameterised by k and d, that for input hypergraph H with maximal cardinality of edge intersections d and integer k either outputs a tree decomposition with ghw(H) ≤ 4k(k+d+1)(2k-1), or rejects, in which case it is guaranteed that ghw(H) > k. Thus, in the special case of hypergraphs of bounded edge intersection, we obtain an FPT O(k³)-approximation algorithm for ghw
Matthias Wagner : author profile
No full textThe author presented on this page has published his 10. article in Angewandte Chemie in the last 10 years
The complexity of pattern counting in directed graphs, parameterised by the outdegree
Get PDFWe study the fixed-parameter tractability of the following fundamental problem: given two directed graphs H→ and G→, count the number of copies of H→ in G→. The standard setting, where the tractability is well understood, uses only |H→| as a parameter. In this paper we adopt as a parameter |H→|+d(G→), where d(G→) is the maximum outdegree of |G→|. Under this parameterisation, we completely characterize the fixed-parameter tractability of the problem in both its non-induced and induced versions through two novel structural parameters, the fractional cover number ρ* and the source number αs. On the one hand we give algorithms with running time f(|H→|,d(G→)) · |G→|ρ*(H→)+O(1) and f(|H→|,d(G→)) · |G→|αs(H→)+O(1) for counting respectively the copies and induced copies of H→ in G→; on the other hand we show that, unless the Exponential Time Hypothesis fails, for any class C→ of directed graphs the restriction of the problem to patterns in C→ is fixed-parameter tractable if and only if ρ*(C→) is bounded (αs(C→) for the induced version). These results explain how the orientation of the pattern can make counting easy or hard, and prove that a classic algorithm by Chiba and Nishizeki and its extensions (Chiba and Nishizeki, SICOMP ’85; Bressan, Algorithmica ’21) are optimal unless ETH fails.
Our proofs consist of several layers of parameterised reductions that preserve the outdegree of the host graph. To start with, we establish a tight connection between counting homomorphisms from H→ to G→ to #CSP, the problem of counting solutions of constraint satisfactions problems, for special classes of patterns that we call canonical DAGs. To lift these results from canonical DAGs to arbitrary directed graphs, we exploit a combination of several ingredients: existing results for #CSPs (Marx JACM 13; Grohe, Marx TALG 14), an extension of graph motif parameters (Curticapean, Dell, Marx STOC 17) to our setting, the introduction of what we call monotone reversible minors, and a careful analysis of quotients of directed graphs in order to relate their adaptive width and fractional hypertreewidth to our novel parameters. Along the route we establish a novel bound of the integrality gap for the fractional independence number of hypergraphs based on adaptive width, which might be of independent interest
Enduring Ambiguity: What Is European Literature? Matthias Nawrat in Conversation with Monika Woltig
Get PDFMatthias Nawrat is a Polish-German author living in Germany born in Opole, Poland. He moved with his family to Bamberg in 1989. He was awarded the Adelbert-von-ChamissoFörderpreis, was nominated for the Deutscher Buchpreis, received the Bremen Literature Prize and the Alfred Döblin Medaille. His most important novels were "Wir zwei allein" (2012), "Die vielen Tode unseres Opas Jurek" (2015), and "Der traurige Gast" (2019).Matthias Nawrat to niemiecki autor polskiego pochodzenia. Matthias Nawrat urodził się w Opolu i wraz z rodziną przeprowadził się w 1989 roku do Bambergu. Uzyskał Nagrodę im. Adelberta von Chamisso (Förderpreis), był nominowany do Niemieckiej Nagrody Książkowej (Deutscher Buchpreis), otrzymał Nagrodę Literacką miasta Bremy i Medal im. Alfreda Döblina. Najważniejsze teksty: "Wir zwei allein" (2012), "Die vielen Tode unseres Opas Jurek" (2015), "Der traurige Gast" (2019).Matthias Nawrat ist ein deutscher Autor polnischer Herkunft. Matthias Nawrat wurde im polnischen Opole geboren und siedelte 1989 mit seiner Familie nach Bamberg über. Er wurde mit dem Adelbert-von-Chamisso-Förderpreis ausgezeichnet, zum Deutschen Buchpreis nominiert und erhielt den Bremer Literaturpreis sowie die Alfred-Döblin-Medaille. Die wichtigsten Texte: "Wir zwei allein" (2012), "Die vielen Tode unseres Opas Jurek" (2015), "Der traurige Gast" (2019)
Baculus Militaris Compendiosus Infanterie Oder Officirers Stab Das ist Ein kurtzer Begrieff der Kriegs Lectionen bey dem Fußvolck gebräuchlich auch nötig : Bestehend in sechserley Exercitien 1. In der Partisan, halber Pique oder Jägerstock. 2. In der Fahn. 3. In der Pique. 4. In der Musqueten. 5. In der Musqueten mit der gabel oben und unten mit einer eiserner spitzen und in der mitten mit einem ein geschrobenen hacken. 6. In Hieb degen/ welcher bey dem fußvolck brauchlich / [Matthias Schlüter]
No full textJohn Matthias
Get PDFPoster promoting author John Matthias reading from his work in the Auditorium, Building 9, University of North Florida.
Poster dimensions: 26.7 cm x 41.8 cmhttps://digitalcommons.unf.edu/performances_print/1013/thumbnail.jp
Patristical Ideas in the Works of Matthias of Janov
Get PDFANGLICKÁ ANOTACE Title: Patristical ideas in the works of Matthias of Janov The thesis treats of the identification of ideas of church fathers in the work and thinking of Matthias of Janov. The thesis consits of three main parts. First part deals with Matthias of Janov in broader context of church tradition. Major political and theological developments that could have an impact on Matthias theological work are presented in this section. Second part introduces life of Matthias of Janov and identifies his major theological contributions. In the third part of the thesis, following explanation of methodology used, the findings of the author are presented. Three areas were selected by the author and researched in view of the identification of possible influance of church fathers in the Matthias of Janov work: the idea of Antichrist, frequent eucharisty and condemnation of idolatry. The findings confirm a strong influance of Augustin and Hieronymus in particular and other early church fathers on the formation of the theology of Matthias of Janov in all three areas of the study. It was also noticed that through the church fathers Matthias of Janov was strongly influenced by neoplatonism which was documented on his idea of "The First Thruth" Key words: Matthias of Janov, church fathers, antichrist, eucharisty,..
Philon von Alexandria, De Abrahamo
No full textPhilons Biographie Abrahams ist eine Werbeschrift für das Judentum – geschrieben in einem politischen Kontext, in dem Juden um ihre Rechte kämpfen mussten. Der vorliegende Band bietet eine Neuübersetzung des Texts mit Einleitung und Anmerkungen sowie sechs erläuternde Essays aus unterschiedlichen Fachperspektiven
Foreign Policy of King Matthias Corvinus from 1464 to 1490
Get PDFOvaj je članak drugi dio rada u kojem se istražuje vrlo kompleksna europska politika ugarsko-hrvatskoga kralja Matijaša Korvina. U ovom se dijelu razmatraju događaji od proljeća 1464. do 1490. godine. U prvom poglavlju članka autor obrađuje pokušaj organiziranja križarskoga pohoda Pija II. protiv Osmanlija 1464. i Matijaševe samostalne akcije radi učvršćivanja jugoistočnih granica kraljevstva. U drugom se poglavlju obrađuje razvoj Matijaševih odnosa s bivšim tastom Jurjem Podjebradskim koji je na kraju doveo do rata (1468–1471). U trećem je poglavlju dan kratak osvrt na pobunu plemstva protiv Matijaševe centralističke vladavine 1472. Četvrto se poglavlje bavi ratom za češko prijestolje (1471–1479) i ponovnim ratom protiv Fridrika III. (1477). U petom poglavlju autor daje kratki pregled Matijaševih odnosa s papinstvom, a u šestom pregled ratovanja s Osmanlijama tijekom sedamdesetih i osamdesetih godina XV. stoljeća. U sedmom poglavlju razmatraju se diplomatske akcije vezane uz traženje Matijaševe nove supruge te njegov brak s Beatricom Aragonskom. U osmom poglavlju autor se bavi Matijaševim ratom s Fridrikom III. za carsku titulu. Deveto je poglavlje posvećeno kraljevoj vanjskoj politici i diplomatskim aktivnostima s Venecijom i talijanskim državama tijekom osamdesetih godina. Deseto poglavlje daje pregled političkih aktivnosti tijekom posljednjih godina njegove vladavine. Jedanaesto poglavlje analizira Matijaševu vojsku. Rad završava kratkim pregledom posljednica kraljeve burne politike.This article is the second part of a longer paper in which the author reviews the very complex foreign policy of Hungarian-Croatian king Matthias Corvinus. In this paper the author analyses major events from Matthias’ coronation in the spring of 1464 until his sudden death in Vienna in the spring of 1490. The whole paper and analysis of events are based on research of various sources and literature. In the first chapter the author describes the failed attempt of Pope Pius II to organize a crusade against the Ottoman Empire in 1464 and Matthias’ own actions against the Turks with the main goal of strengthening his southeastern borders. In the second chapter the author analyses the conflict between Matthias and his ex-father-in-law, George of Poděbrady, and the war between them (1468–1471). In the third chapter the author gives a short overview of the uprising of magnates and the aristocracy against the central rule of King Matthias (1472). The fourth chapter deals with the war for the Bohemian throne from 1471 to 1479 and the war against Frederick III in 1477. In the next chapter the author gives a brief overview of the diplomatic relations between popes and Matthias Corvinus over a longer period of time, from 1464 to 1490. The main subject of the sixth chapter is the war against the Ottoman Empire during the seventh and eighth decade of the 15th century. In the seventh chapter the author describes Matthias’ search for his next wife and his marriage to Beatrice of Aragon. In the following chapter the author reviews Matthias’ new war against Frederick III for the title of the German Empire. The ninth chapter is a brief overview of Matthias’ foreign policy in the Italian states and Venice during the last decade of his life. The tenth chapter is dedicated to the final years of Matthias’ life. The next chapter analyses one of the most important segments of his foreign policy – his army. This article ends with short overview of the events which happened after the death of King Matthias and the consequences of his stormy policy
- …
