@misc{BeisegelDenkertKoehleretal., author = {Beisegel, Jesse and Denkert, Carolin and K{\"o}hler, Ekkehard and Krnc, Matjaž and Pivač, Nevena and Scheffler, Robert and Strehler, Martin}, title = {Recognizing Graph Search Trees}, series = {arXiv.org}, journal = {arXiv.org}, pages = {23}, language = {en} } @misc{BeisegelDenkertKoehleretal., author = {Beisegel, Jesse and Denkert, Carolin and K{\"o}hler, Ekkehard and Krnc, Matjaž and Pivač, Nevena and Scheffler, Robert and Strehler, Martin}, title = {On the End-Vertex Problem of Graph Searches}, series = {Discrete Mathematics \& Theoretical Computer Science}, volume = {21}, journal = {Discrete Mathematics \& Theoretical Computer Science}, number = {1}, issn = {1365-8050}, language = {en} } @misc{BeisegelChiarelliKoehleretal., author = {Beisegel, Jesse and Chiarelli, Nina and K{\"o}hler, Ekkehard and Krnc, Matjaž and Milanič, Martin and Pivač, Nevena and Scheffler, Robert and Strehler, Martin}, title = {Edge Elimination and Weighted Graph Classes}, series = {Graph-Theoretic Concepts in Computer Science - 46th International Workshop, {WG} 2020, Leeds, UK, June 24-26, 2020}, journal = {Graph-Theoretic Concepts in Computer Science - 46th International Workshop, {WG} 2020, Leeds, UK, June 24-26, 2020}, editor = {Adler, Isolde and M{\"u}ller, Haiko}, publisher = {Springer}, address = {Cham}, isbn = {978-3-030-60439-4}, issn = {1611-3349}, doi = {10.1007/978-3-030-60440-0_11}, pages = {134 -- 147}, language = {en} } @misc{BeisegelKoehlerScheffleretal., author = {Beisegel, Jesse and K{\"o}hler, Ekkehard and Scheffler, Robert and Strehler, Martin}, title = {Linear Time LexDFS on Chordal Graphs}, series = {28th Annual European Symposium on Algorithms (ESA) 2020, September 7-9, 2020, Pisa, Italy)}, volume = {173}, journal = {28th Annual European Symposium on Algorithms (ESA) 2020, September 7-9, 2020, Pisa, Italy)}, publisher = {Schloss Dagstuhl, Leibnitz Zentrum f{\"u}r Informatik}, doi = {10.4230/LIPIcs.ESA.2020.13}, url = {http://nbn-resolving.de/urn:nbn:de:0030-drops-128790}, pages = {13:1 -- 13:13}, language = {en} } @misc{BeisegelDenkertKoehleretal., author = {Beisegel, Jesse and Denkert, Carolin and K{\"o}hler, Ekkehard and Krnc, Matjaž and Pivač, Nevena and Scheffler, Robert and Strehler, Martin}, title = {Recognizing Graph Search Trees}, series = {The proceedings of Lagos 2019, the tenth Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS 2019) 2-7 June 2019, Belo Horizonte, Brazil}, journal = {The proceedings of Lagos 2019, the tenth Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS 2019) 2-7 June 2019, Belo Horizonte, Brazil}, editor = {Coutinho, Gabriel and Kohayakawa, Yoshiharu and dos Santos, Vinicius and Urrutia, Sebasti{\´a}n}, publisher = {Elsevier}, issn = {1571-0661}, doi = {10.1016/j.entcs.2019.08.010}, pages = {99 -- 110}, language = {en} } @misc{BeisegelChudnovskyGurvichetal., author = {Beisegel, Jesse and Chudnovsky, Maria and Gurvich, Vladimir and Milanič, Martin and Servatius, Mary}, title = {Avoidable Vertices and Edges in Graphs}, series = {Algorithms and Data Structures : 16th International Symposium, WADS 2019, Edmonton, AB, Canada, August 5-7, 2019, Proceedings}, journal = {Algorithms and Data Structures : 16th International Symposium, WADS 2019, Edmonton, AB, Canada, August 5-7, 2019, Proceedings}, editor = {Friggstad, Zachary and Sack, J{\"o}rg-R{\"u}diger and Salavatipour, Mohammad}, publisher = {Springer}, address = {Cham}, isbn = {978-3-030-24765-2}, issn = {0302-9743}, doi = {10.1007/978-3-030-24766-9_10}, pages = {126 -- 139}, language = {en} } @misc{Beisegel, author = {Beisegel, Jesse}, title = {Characterising AT-free Graphs with BFS}, series = {Graph-Theoretic Concepts in Computer Science - 44th International Workshop, WG 2018, Cottbus, Germany, June 27-29, 2018, Proceedings}, journal = {Graph-Theoretic Concepts in Computer Science - 44th International Workshop, WG 2018, Cottbus, Germany, June 27-29, 2018, Proceedings}, editor = {Brandst{\"a}dt, Andreas and K{\"o}hler, Ekkehard and Meer, Klaus}, publisher = {Springer}, address = {Cham}, isbn = {978-3-030-00255-8}, issn = {0302-9743}, doi = {10.1007/978-3-030-00256-5_2}, pages = {15 -- 26}, language = {en} } @misc{BeisegelDenkertKoehleretal., author = {Beisegel, Jesse and Denkert, Carolin and K{\"o}hler, Ekkehard and Krnc, Matjaž and Pivač, Nevena and Scheffler, Robert and Strehler, Martin}, title = {The Recognition Problem of Graph Search Trees}, series = {SIAM Journal on Discrete Mathematics}, volume = {35}, journal = {SIAM Journal on Discrete Mathematics}, number = {2}, issn = {1095-7146}, doi = {10.1137/20M1313301}, pages = {1418 -- 1446}, language = {en} } @techreport{BeisegelBuhlIzaretal., author = {Beisegel, Jesse and Buhl, Johannes and Izar, Rameez and Schmidt, Johannes and Bambach, Markus and F{\"u}genschuh, Armin}, title = {Mixed-integer programming for additive manufacturing}, editor = {F{\"u}genschuh, Armin}, address = {Cottbus}, doi = {10.26127/BTUOpen-5731}, pages = {28}, language = {en} } @incollection{BeisegelBuhlIsraretal., author = {Beisegel, Jesse and Buhl, Johannes and Israr, Rameez and Schmidt, Johannes and Bambach, Martin and F{\"u}genschuh, Armin}, title = {Mixed-Integer Programming Models for Two Metal Additive Manufacturing Methods}, series = {Mathematical Methods for Objects Reconstruction}, booktitle = {Mathematical Methods for Objects Reconstruction}, editor = {Cristiani, Emiliano and Falcone, Maurizio and Tozza, Silvia}, publisher = {Springer}, address = {Heidelberg}, isbn = {978-981-9907-75-5}, pages = {121 -- 155}, language = {en} } @misc{MaierKuhnBeisegeletal., author = {Maier, Isidor Konrad and Kuhn, Johannes and Beisegel, Jesse and Huber-Liebl, Markus and Wolff, Matthias}, title = {Minimalist Grammar: Construction without Overgeneration}, series = {arXiv}, journal = {arXiv}, doi = {10.48550/arXiv.2311.01820}, pages = {51}, abstract = {In this paper we give instructions on how to write a minimalist grammar (MG). In order to present the instructions as an algorithm, we use a variant of context free grammars (CFG) as an input format. We can exclude overgeneration, if the CFG has no recursion, i.e. no non-terminal can (indirectly) derive to a right-hand side containing itself. The constructed MGs utilize licensors/-ees as a special way of exception handling. A CFG format for a derivation A_eats_B↦∗peter_eats_apples, where A and B generate noun phrases, normally leads to overgeneration, e.\,g., i_eats_apples. In order to avoid overgeneration, a CFG would need many non-terminal symbols and rules, that mainly produce the same word, just to handle exceptions. In our MGs however, we can summarize CFG rules that produce the same word in one item and handle exceptions by a proper distribution of licensees/-ors. The difficulty with this technique is that in most generations the majority of licensees/-ors is not needed, but still has to be triggered somehow. We solve this problem with ϵ-items called \emph{adapters}.}, language = {en} } @misc{BeisegelChiarelliKoehleretal., author = {Beisegel, Jesse and Chiarelli, Nina and K{\"o}hler, Ekkehard and Milanič, Martin and Muršič, Peter and Scheffler, Robert}, title = {The simultaneous interval number: a new width parameter that measures the similarity to interval graphs}, series = {19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)}, journal = {19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl}, isbn = {978-3-95977-318-8}, doi = {10.4230/LIPIcs.SWAT.2024.7}, pages = {7:1 -- 7:20}, language = {en} } @misc{BeisegelKoehlerRatajczaketal., author = {Beisegel, Jesse and K{\"o}hler, Ekkehard and Ratajczak, Fabienne and Scheffler, Robert and Strehler, Martin}, title = {Graph search trees and the intermezzo problem}, series = {49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)}, journal = {49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)}, editor = {Kr{\´a}lovič, Rastislav and Kučera, Anton{\´i}n}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl}, isbn = {978-3-95977-335-5}, doi = {10.4230/LIPICS.MFCS.2024.22}, pages = {22:1 -- 22:18}, language = {en} } @misc{BeisegelRatajczakScheffler, author = {Beisegel, Jesse and Ratajczak, Fabienne and Scheffler, Robert}, title = {Computing hamiltonian paths with partial order restrictions}, series = {ACM Transactions on Computation Theory}, volume = {17}, journal = {ACM Transactions on Computation Theory}, number = {1}, issn = {1942-3454}, doi = {10.1145/3711844}, pages = {1 -- 24}, abstract = {When solving the Hamiltonian path problem it seems natural to be given additional precedence constraints for the order in which the vertices are visited. For example, one could decide whether a Hamiltonian path exists for a fixed starting point, or that some vertices are visited before another vertex. We consider the problem of finding a Hamiltonian path that observes all precedence constraints given in a partial order on the vertex set. We show that this problem is NP-complete even if restricted to complete bipartite graphs and posets of height 2. In contrast, for posets of width k there is a known O(k^2 n^k) algorithm for arbitrary graphs with n vertices. We show that it is unlikely that the running time of this algorithm can be improved significantly, i.e., there is no f(k) n^o(k) time algorithm under the assumption of the Exponential Time Hypothesis. Furthermore, for the class of outerplanar graphs, we give an O(n^2) algorithm for arbitrary posets.}, language = {en} } @misc{BeisegelKoehlerScheffleretal., author = {Beisegel, Jesse and K{\"o}hler, Ekkehard and Scheffler, Robert and Strehler, Martin}, title = {Certifying fully dynamic algorithms for recognition and Hamiltonicity of Threshold and Chain Graphs}, series = {Algorithmica}, volume = {85}, journal = {Algorithmica}, number = {8}, issn = {0178-4617}, doi = {10.1007/s00453-023-01107-1}, pages = {2454 -- 2481}, language = {en} } @misc{BeisegelKlostKnorretal., author = {Beisegel, Jesse and Klost, Katharina and Knorr, Kristin and Ratajczak, Fabienne and Scheffler, Robert}, title = {A graph width perspective on partially ordered Hamiltonian paths and cycles II : vertex and edge deletion numbers}, series = {20th International Symposium on Parameterized and Exact Computation (IPEC 2025)}, journal = {20th International Symposium on Parameterized and Exact Computation (IPEC 2025)}, editor = {Agrawal, Akanksha and van Leeuwen, Erik Jan}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik}, address = {Wadern}, isbn = {978-3-95977-407-9}, doi = {10.4230/LIPIcs.IPEC.2025.30}, url = {http://nbn-resolving.de/urn:nbn:de:0030-drops-251623}, pages = {30:1 -- 30:19}, abstract = {We consider the problem of finding a Hamiltonian path or cycle with precedence constraints in the form of a partial order on the vertex set. We study the complexity for graph width parameters for which the ordinary problems Hamiltonian Path and Hamiltonian Cycle are in FPT. In particular, we focus on parameters that describe how many vertices and edges have to be deleted to become a member of a certain graph class. We show that the problems are W[1]-hard for such restricted cases as vertex distance to path and vertex distance to clique. We complement these results by showing that the problems can be solved in XP time for vertex distance to outerplanar and vertex distance to block. Furthermore, we present some FPT algorithms, e.g., for edge distance to block. Additionally, we prove para-NP-hardness when considered with the edge clique cover number.}, language = {en} }