{"id":5488,"date":"2021-02-17T07:45:48","date_gmt":"2021-02-17T07:45:48","guid":{"rendered":"https:\/\/verlag.tu-berlin.de\/produkt\/empty-product-container-220\/"},"modified":"2021-02-17T09:46:49","modified_gmt":"2021-02-17T08:46:49","slug":"978-3-7983-2705-4","status":"publish","type":"product","link":"https:\/\/verlag.tu-berlin.de\/en\/produkt\/978-3-7983-2705-4\/","title":{"rendered":"Fixed-Parameter Linear-Time Algorithms for NP-hard Graph and Hypergraph Problems Arising in Industrial Applications"},"content":{"rendered":"<p> This thesis aims for the development of efficient algorithms to exactly solve four selected NP-hard graph and hypergraph problems arising in the fields of scheduling, steel manufactoring, software engineering, radio frequency allocation, computer-aided circuit design, and social network analysis. NP-hard problems presumably cannot be solved exactly in a running time growing only polynomially with the input size. In order to still solve the considered problems efficiently, this thesis develops linear-time data reduction and fixed-parameter linear-time algorithms\u2014algorithms that can be proven to run in linear time if certain parameters of the problem instances are constant. Besides proving linear worst-case running times, the efficiency of most of the developed algorithms is evaluated experimentally. Moreover, the limits of fixed-parameter linear-time algorithms and provably efficient and effective data reduction are shown.<\/p>","protected":false},"excerpt":{"rendered":"<p>This thesis aims for the development of efficient algorithms to exactly solve four selected NP-hard graph and hypergraph problems arising in the fields of scheduling, steel manufactoring, software engineering, radio frequency allocation, computer-aided circuit design, and social network analysis. NP-hard problems presumably cannot be solved exactly in a running time growing only polynomially with the input size. In order to still solve the considered problems efficiently, this thesis develops linear-time data reduction and fixed-parameter linear-time algorithms\u2014algorithms that can be proven to run in linear time if certain parameters of the problem instances are constant. Besides proving linear worst-case running times, the efficiency of most of the developed algorithms is evaluated experimentally. Moreover, the limits of fixed-parameter linear-time algorithms and provably efficient and effective data reduction are shown.<\/p>\n","protected":false},"featured_media":1139,"comment_status":"open","ping_status":"closed","template":"","meta":{"_acf_changed":false},"class_list":["post-5488","product","type-product","status-publish","has-post-thumbnail","hentry","product_cat-institut-fuer-softwaretechnik-und-theoretische-informatik","product_tag-ablaufplanung-automaten-clustering-datenreduktion-exakte-algorithmen-automata-clustering-data-reduction-exact-algorithms-scheduling","autor-rene-van-bevern","reihe-foundations-of-computing","edition-universitaetsverlag-tu-berlin"],"acf":[],"_links":{"self":[{"href":"https:\/\/verlag.tu-berlin.de\/en\/wp-json\/wp\/v2\/product\/5488","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/verlag.tu-berlin.de\/en\/wp-json\/wp\/v2\/product"}],"about":[{"href":"https:\/\/verlag.tu-berlin.de\/en\/wp-json\/wp\/v2\/types\/product"}],"replies":[{"embeddable":true,"href":"https:\/\/verlag.tu-berlin.de\/en\/wp-json\/wp\/v2\/comments?post=5488"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/verlag.tu-berlin.de\/en\/wp-json\/wp\/v2\/media\/1139"}],"wp:attachment":[{"href":"https:\/\/verlag.tu-berlin.de\/en\/wp-json\/wp\/v2\/media?parent=5488"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}