Zobrazeno 1 - 10
of 207
pro vyhledávání: '"P. Jaffke"'
Autor:
A. Chyzh, P. Jaffke, C.Y. Wu, R.A. Henderson, P. Talou, I. Stetcu, J. Henderson, M.Q. Buckner, S.A. Sheets, R. Hughes, B. Wang, J.L. Ullmann, S. Mosby, T.A. Bredeweg, A.C. Hayes-Sterbenz, J.M. O'Donnell
Publikováno v:
Physics Letters B, Vol 782, Iss , Pp 652-656 (2018)
Prompt γ-ray spectra were measured for the spontaneous fission of 240,242Pu and the neutron-induced fission of 239,241Pu with incident neutron energies ranging from thermal to about 100 keV. Measurements were made using the Detector for Advanced Neu
Externí odkaz:
https://doaj.org/article/342eafa31b6c4bb0b9f4334237c74e51
We revisit a graph width parameter that we dub bipartite treewidth, along with its associated graph decomposition that we call bipartite tree decomposition. Bipartite treewidth can be seen as a common generalization of treewidth and the odd cycle tra
Externí odkaz:
http://arxiv.org/abs/2309.07754
Autor:
Bodlaender, Hans L., Bonnet, Édouard, Jaffke, Lars, Knop, Dušan, Lima, Paloma T., Milanič, Martin, Ordyniak, Sebastian, Pandey, Sukanya, Suchý, Ondřej
In this paper, we give a very simple proof that Treewidth is NP-complete; this proof also shows NP-completeness on the class of co-bipartite graphs. We then improve the result by Bodlaender and Thilikos from 1997 that Treewidth is NP-complete on grap
Externí odkaz:
http://arxiv.org/abs/2301.10031
We show that the $b$-Coloring problem is complete for the class XNLP when parameterized by the pathwidth of the input graph. Besides determining the precise parameterized complexity of this problem, this implies that b-Coloring parameterized by pathw
Externí odkaz:
http://arxiv.org/abs/2209.07772
Publikováno v:
Proceedings: ACM-SIAM Symposium on Discrete Algorithms, SODA 2023
We study a generalization of the classic Global Min-Cut problem, called Global Label Min-Cut (or sometimes Global Hedge Min-Cut): the edges of the input (multi)graph are labeled (or partitioned into color classes or hedges), and removing all edges of
Externí odkaz:
http://arxiv.org/abs/2207.07426
Autor:
Hatzel, Meike, Jaffke, Lars, Lima, Paloma T., Masařík, Tomáš, Pilipczuk, Marcin, Sharma, Roohani, Sorge, Manuel
Publikováno v:
Proceedings: ACM-SIAM Symposium on Discrete Algorithms, SODA 2023
We show fixed-parameter tractability of the Directed Multicut problem with three terminal pairs (with a randomized algorithm). This problem, given a directed graph $G$, pairs of vertices (called terminals) $(s_1,t_1)$, $(s_2,t_2)$, and $(s_3,t_3)$, a
Externí odkaz:
http://arxiv.org/abs/2207.07425
Autor:
Jaffke, Lars, Lima, Paloma T.
We determine the maximum number of edges that a planar graph can have as a function of its maximum degree and matching number.
Externí odkaz:
http://arxiv.org/abs/2207.03130
Autor:
Gajarský, Jakub, Jaffke, Lars, Lima, Paloma T., Novotná, Jana, Pilipczuk, Marcin, Rzążewski, Paweł, Souza, Uéverton S.
We confirm a conjecture of Gartland and Lokshtanov [arXiv:2007.08761]: if for a hereditary graph class $\mathcal{G}$ there exists a constant $k$ such that no member of $\mathcal{G}$ contains a $k$-creature as an induced subgraph or a $k$-skinny-ladde
Externí odkaz:
http://arxiv.org/abs/2205.01191
We introduce a logic called distance neighborhood logic with acyclicity and connectivity constraints ($\mathsf{A\&C~DN}$ for short) which extends existential $\mathsf{MSO_1}$ with predicates for querying neighborhoods of vertex sets and for verifying
Externí odkaz:
http://arxiv.org/abs/2202.13335
In this paper, we showcase the class XNLP as a natural place for many hard problems parameterized by linear width measures. This strengthens existing $W[1]$-hardness proofs for these problems, since XNLP-hardness implies $W[t]$-hardness for all $t$.
Externí odkaz:
http://arxiv.org/abs/2201.13119