<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>26460</id>
    <completedYear/>
    <publishedYear>2020</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>134</pageFirst>
    <pageLast>147</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>conferenceobject_ref</type>
    <publisherName>Springer</publisherName>
    <publisherPlace>Cham</publisherPlace>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2020-12-10</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Edge Elimination and Weighted Graph Classes</title>
    <parentTitle language="eng">Graph-Theoretic Concepts in Computer Science - 46th International                Workshop, {WG} 2020, Leeds, UK, June 24-26, 2020</parentTitle>
    <identifier type="doi">10.1007/978-3-030-60440-0_11</identifier>
    <identifier type="isbn">978-3-030-60439-4</identifier>
    <identifier type="isbn">978-3-030-60440-0</identifier>
    <identifier type="issn">1611-3349</identifier>
    <identifier type="issn">0302-9743</identifier>
    <enrichment key="UBICOseries">Lecture Notes in Computer Science ; 12301</enrichment>
    <enrichment key="BTU">an der BTU erstellt / created at BTU</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <enrichment key="Fprofil">1 Energiewende und Dekarbonisierung / Energy Transition and Decarbonisation</enrichment>
    <enrichment key="Fprofil">4 Künstliche Intelligenz und Sensorik / Artificial Intelligence and Sensor Technology</enrichment>
    <author>
      <firstName>Jesse</firstName>
      <lastName>Beisegel</lastName>
    </author>
    <editor>
      <firstName>Isolde</firstName>
      <lastName>Adler</lastName>
    </editor>
    <submitter>
      <firstName>Diana</firstName>
      <lastName>Hübner</lastName>
    </submitter>
    <author>
      <firstName>Nina</firstName>
      <lastName>Chiarelli</lastName>
    </author>
    <editor>
      <firstName>Haiko</firstName>
      <lastName>Müller</lastName>
    </editor>
    <author>
      <firstName>Ekkehard</firstName>
      <lastName>Köhler</lastName>
    </author>
    <author>
      <firstName>Matjaž</firstName>
      <lastName>Krnc</lastName>
    </author>
    <author>
      <firstName>Martin</firstName>
      <lastName>Milanič</lastName>
    </author>
    <author>
      <firstName>Nevena</firstName>
      <lastName>Pivač</lastName>
    </author>
    <author>
      <firstName>Robert</firstName>
      <lastName>Scheffler</lastName>
    </author>
    <author>
      <firstName>Martin</firstName>
      <lastName>Strehler</lastName>
    </author>
    <collection role="institutes" number="1304">FG Diskrete Mathematik und Grundlagen der Informatik</collection>
    <collection role="institutes" number="1307">FG Ingenieurmathematik und Numerik der Optimierung</collection>
  </doc>
  <doc>
    <id>26444</id>
    <completedYear/>
    <publishedYear>2020</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>13:1</pageFirst>
    <pageLast>13:13</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>173</volume>
    <type>conferenceobject_ref</type>
    <publisherName>Schloss Dagstuhl, Leibnitz Zentrum für Informatik</publisherName>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2020-12-03</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Linear Time LexDFS on Chordal Graphs</title>
    <parentTitle language="eng">28th Annual European Symposium on Algorithms (ESA) 2020, September 7-9, 2020, Pisa, Italy)</parentTitle>
    <identifier type="urn">urn:nbn:de:0030-drops-128790</identifier>
    <identifier type="doi">10.4230/LIPIcs.ESA.2020.13</identifier>
    <identifier type="url">https://drops.dagstuhl.de/opus/volltexte/2020/12879</identifier>
    <enrichment key="BTU">an der BTU erstellt / created at BTU</enrichment>
    <enrichment key="Fprofil">1 Energiewende und Dekarbonisierung / Energy Transition and Decarbonisation</enrichment>
    <enrichment key="Fprofil">4 Künstliche Intelligenz und Sensorik / Artificial Intelligence and Sensor Technology</enrichment>
    <author>
      <firstName>Jesse</firstName>
      <lastName>Beisegel</lastName>
    </author>
    <submitter>
      <firstName>Diana</firstName>
      <lastName>Hübner</lastName>
    </submitter>
    <author>
      <firstName>Ekkehard</firstName>
      <lastName>Köhler</lastName>
    </author>
    <author>
      <firstName>Robert</firstName>
      <lastName>Scheffler</lastName>
    </author>
    <author>
      <firstName>Martin</firstName>
      <lastName>Strehler</lastName>
    </author>
    <collection role="institutes" number="1304">FG Diskrete Mathematik und Grundlagen der Informatik</collection>
    <collection role="institutes" number="1307">FG Ingenieurmathematik und Numerik der Optimierung</collection>
  </doc>
  <doc>
    <id>35615</id>
    <completedYear/>
    <publishedYear>2025</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>1</pageFirst>
    <pageLast>24</pageLast>
    <pageNumber/>
    <edition/>
    <issue>1</issue>
    <volume>17</volume>
    <type>articler</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2025-03-26</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Computing hamiltonian paths with partial order restrictions</title>
    <abstract language="eng">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.</abstract>
    <parentTitle language="eng">ACM Transactions on Computation Theory</parentTitle>
    <identifier type="issn">1942-3454</identifier>
    <identifier type="url">https://dl.acm.org/doi/10.1145/3711844</identifier>
    <identifier type="doi">10.1145/3711844</identifier>
    <enrichment key="Fprofil">1 Energiewende und Dekarbonisierung / Energy Transition and Decarbonisation</enrichment>
    <enrichment key="Fprofil">4 Künstliche Intelligenz und Sensorik / Artificial Intelligence and Sensor Technology</enrichment>
    <enrichment key="BTU">an der BTU erstellt / created at BTU</enrichment>
    <enrichment key="Artikelnummer">5</enrichment>
    <enrichment key="Publikationsweg">Open Access</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <author>
      <firstName>Jesse</firstName>
      <lastName>Beisegel</lastName>
    </author>
    <submitter>
      <firstName>Robert</firstName>
      <lastName>Scheffler</lastName>
    </submitter>
    <author>
      <firstName>Fabienne</firstName>
      <lastName>Ratajczak</lastName>
    </author>
    <author>
      <firstName>Robert</firstName>
      <lastName>Scheffler</lastName>
    </author>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Hamiltonian path</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Partial order</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Outerplanar graph</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Partial search order</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>TSP-PC</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Parameterized complexity</value>
    </subject>
    <collection role="institutes" number="1304">FG Diskrete Mathematik und Grundlagen der Informatik</collection>
    <collection role="institutes" number="1307">FG Ingenieurmathematik und Numerik der Optimierung</collection>
  </doc>
  <doc>
    <id>37126</id>
    <completedYear/>
    <publishedYear>2025</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>30:1</pageFirst>
    <pageLast>30:19</pageLast>
    <pageNumber>19</pageNumber>
    <edition/>
    <issue/>
    <volume/>
    <type>conferenceobject_ref</type>
    <publisherName>Schloss Dagstuhl – Leibniz-Zentrum für Informatik</publisherName>
    <publisherPlace>Wadern</publisherPlace>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2025-12-17</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">A graph width perspective on partially ordered Hamiltonian paths and cycles II : vertex and edge deletion numbers</title>
    <abstract language="eng">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.</abstract>
    <parentTitle language="eng">20th International Symposium on Parameterized and Exact Computation (IPEC 2025)</parentTitle>
    <identifier type="isbn">978-3-95977-407-9</identifier>
    <identifier type="url">https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.30</identifier>
    <identifier type="urn">urn:nbn:de:0030-drops-251623</identifier>
    <identifier type="doi">10.4230/LIPIcs.IPEC.2025.30</identifier>
    <enrichment key="Fprofil">1 Energiewende und Dekarbonisierung / Energy Transition and Decarbonisation</enrichment>
    <enrichment key="Fprofil">4 Künstliche Intelligenz und Sensorik / Artificial Intelligence and Sensor Technology</enrichment>
    <enrichment key="UBICOseries">Leibniz International Proceedings in Informatics ; 358</enrichment>
    <enrichment key="BTU">an der BTU erstellt / created at BTU</enrichment>
    <enrichment key="Artikelnummer">30</enrichment>
    <enrichment key="Publikationsweg">Open Access</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <enrichment key="opus.doi.autoCreate">false</enrichment>
    <enrichment key="opus.urn.autoCreate">false</enrichment>
    <licence>Creative Commons - CC BY - Namensnennung 4.0 International</licence>
    <author>
      <firstName>Jesse</firstName>
      <lastName>Beisegel</lastName>
    </author>
    <editor>
      <firstName>Akanksha</firstName>
      <lastName>Agrawal</lastName>
    </editor>
    <submitter>
      <firstName>Robert</firstName>
      <lastName>Scheffler</lastName>
    </submitter>
    <author>
      <firstName>Katharina</firstName>
      <lastName>Klost</lastName>
    </author>
    <editor>
      <firstName>Erik Jan</firstName>
      <lastName>van Leeuwen</lastName>
    </editor>
    <author>
      <firstName>Kristin</firstName>
      <lastName>Knorr</lastName>
    </author>
    <author>
      <firstName>Fabienne</firstName>
      <lastName>Ratajczak</lastName>
    </author>
    <author>
      <firstName>Robert</firstName>
      <lastName>Scheffler</lastName>
    </author>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Hamiltonian path</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Hamiltonian cycle</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>partial order</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>graph width parameter</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>parameterized complexity</value>
    </subject>
    <collection role="institutes" number="1304">FG Diskrete Mathematik und Grundlagen der Informatik</collection>
    <collection role="institutes" number="1307">FG Ingenieurmathematik und Numerik der Optimierung</collection>
  </doc>
</export-example>
