@phdthesis{Maerz2016, author = {M{\"a}rz, Armin}, title = {Three Essays on Understanding Mobile Consumer Behavior: Business Models, Perceptions, and Features}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-3948}, school = {Universit{\"a}t Passau}, pages = {145 S.}, year = {2016}, abstract = {For about a decade, consumers have been carrying the Internet in their pockets. The rapid penetration of modern smartphones has meant that more than two-thirds of the people in the West can access and use online resources, anytime and anywhere. Consumers also can communicate and share their consumption experiences instantaneously. Platforms reach users for time-critical events through highly personal communication channels, in the sense that smartphones serve as constant companions. Many mobile applications and their basic services and contents also are available for free. The digital and mobile worlds thus are changing the very means of communication, suggesting the powerful need for marketing research and practice to find the opportunities and meet the challenges of the mobile Internet. In particular, scientific investigations are required to describe new business models in the free e-service industry and the consumer behavior affected by mobile features. This thesis examines these topics in three essays. Study 1 considers business models that offer their services without charge. Offering services for free is symptomatic of not only mobile apps (90\% of all apps are available for free) but the digital economy in general. For companies offering free e-services, this situation raises several important questions, in that, without any access device restrictions, how do customers of free e-services contribute value without paying? What are the nature and dynamics of nonmonetary value contributions by nonpaying customers? With a literature review and interviews with senior executives of free e-service providers, Study 1 presents a comprehensive overview of nonmonetary value contributions in the free e-service sector, including word of mouth, co-production, and network effects. Moreover, adding attention and data into this framework reveals two further aspects that have not been addressed in prior customer value research. By putting the findings in the context of the existing literature on customer value and customer engagement, this study sheds light on the complex processes of value creation in the emerging e-service sector, while advancing marketing and service research in general. Study 2 deepens the findings from the first study; specifically, the focus is on the way that mobile users co-produce content and how this contribution is perceived by recipients in the network. With field data and a scenario experiment, this study demonstrates that recipients appreciate mobile-generated customer reviews fundamentally differently from other reviews. In particular, they discount the helpfulness of mobile reviews, due to their text-specific content and style particularities. The very fact that a review has been identified as written on a mobile device also lowers recipients' perceptions of its value. Recipients use information about the device as a source cue to assess their compatibility with the review contribution channel. If they perceive themselves as compatible with the method used to generate the review (mobile or non-mobile), recipients regard the review as more helpful, because they attribute the review to the quality of the reviewed subject. If they perceive it as incompatible though, recipients assume that the review reflects the personal dispositions of the reviewer and discount its helpfulness. Finally, Study 3 takes up the attention and cross-market network effects in a mobile setting; these were two nonmonetary dimensions identified by Study 1. Platform providers should develop measures to draw the attention of nonpaying customers to the offers of their paying customers. One attention-grabbing mobile-specific feature is push notifications to the device, which provide information about temporally or spatially relevant events. More concretely, Study 3 investigates how mobile push notifications remind users of upcoming deadlines in online auctions and therefore improve late bidding success. Late bidding is a prevalent strategy, in which bidders submit their bids at the very end of an online auction. This research uses field data about an online auction platform to demonstrate that late bidders use these mobile push notifications more frequently than do bidders with different bidding patterns. Within the group of late bidders, the chance to win an auction increases with their use of push notifications. After a mobile push notification, late bidders submit bids through mobile devices but also through non-mobile channels. Less experienced late bidders also benefit from push notifications, which increase their chances of success. In summary, this dissertation contributes to an enhanced understanding of mobile consumer behavior by using various methods, including qualitative interviews, field observations, and online experiments. From a theoretical perspective, it contributes to current knowledge about nonmonetary costumer value contributions in general and their role in mobile settings in particular. This thesis highlights the role of mobile devices in co-production and perceptions of co-produced content. It also reveals how mobile-specific interactive features, like push notifications, affect late bidding efficiency. Therefore, it specifies the role of mobile devices in cross-market effects, in that they enable the platform to direct the relationship between buyers and sellers. The insights presented herein encourage managers to reevaluate their current practices, think about whether they should label co-produced content as generated through a mobile channel or not, and contemplate whether to develop mobile push notifications as helpful features for users (not as intrusive marketing messages).}, language = {en} } @phdthesis{Alsarem2016, author = {Alsarem, Mazen}, title = {Semantic Snippets via Query-Biased Ranking of Linked Data Entities}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-3959}, school = {Universit{\"a}t Passau}, pages = {148 S.}, year = {2016}, abstract = {In our knowledge-driven society, the acquisition and the transfer of knowledge play a principal role. Web search engines are somehow tools for knowledge acquisition and transfer from the web to the user. The search engine results page (SERP) consists mainly of a list of links and snippets (excerpts from the results). The snippets are used to express, as efficiently as possible, the way a web page may be relevant to the query. As an extension of the existing web, the semantic web or "web 3.0" is designed to convert the presently available web of unstructured documents into a web of data consumable by both human and machines. The resulting web of data and the current web of documents coexist and interconnect via multiple mechanisms, such as the embedded structured data, or the automatic annotation. In this thesis, we introduce a new interactive artifact for the SERP: the "Semantic Snippet". Semantic Snippets rely on the coexistence of the two webs to facilitate the transfer of knowledge to the user thanks to a semantic contextualization of the user's information need. It makes apparent the relationships between the information need and the most relevant entities present in the web page. The generation of semantic snippets is mainly based on the automatic annotation of the LOD1's entities in web pages. The annotated entities have different level of impor- tance, usefulness and relevance. Even with state of the art solutions for the automatic annotations of LOD entities within web pages, there is still a lot of noise in the form of erroneous or off-topic annotations. Therefore, we propose a query-biased algorithm (LDRANK) for the ranking of these entities. LDRANK adopts a strategy based on the linear consensual combination of several sources of prior knowledge (any form of con- textual knowledge, like the textual descriptions for the nodes of the graph) to modify a PageRank-like algorithm. For generating semantic snippets, we use LDRANK to find the more relevant entities in the web page. Then, we use a supervised learning algorithm to link each selected entity to excerpts from the web page that highlight the relationship between the entity and the original information need. In order to evaluate our semantic snippets, we integrate them in ENsEN (Enhanced Search Engine), a software system that enhances the SERP with semantic snippets. Finally, we use crowdsourcing to evaluate the usefulness and the efficiency of ENsEN.}, subject = {World Wide Web 3.0}, language = {en} } @phdthesis{Tomashevich2016, author = {Tomashevich, Victor}, title = {Fault Tolerance Aspects of Virtual Massive MIMO Systems}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-4047}, school = {Universit{\"a}t Passau}, pages = {183}, year = {2016}, abstract = {Employment of a very large number of antennas is seen as the key technology to provide future users with very high data rates. At the same time, the implementation complexity will rise due to large memories required and sophisticated signal processing algorithms employed. Continuous technology downscaling allows implementation of such complex digital designs. At the same time, its inherent variability and vulnerability to physical disturbances violate the assumption of perfectly reliable hardware operation. This work considers Unique Word OFDM which represents the alternative to the standard Cyclic Prefix OFDM providing superior detection quality. The generalization of Unique Word OFDM to a MIMO system is performed which allows interpretation as a virtual massive MIMO system with only few physical antennas. Detection methods for the introduced generalization are discussed and their performance is quantified. Because of the large memory size required, linear detection represents the cost and performance effective solution. The possible memory errors due to radiation effects or voltage scaling are addressed and the nonlinear MMSE detection algorithm is proposed. This algorithm keeps track of the memory errors and is able to significantly mitigate their effect on the quality of the estimated data. Apart of memory issues, reliability of the actual computational hardware which constitutes the receiver is of concern in this work. An own implementation of the MMSE Sorted Givens Rotations is subjected to transient fault injection. The impact of faults in various parts of the implemented circuit on the detection performance is quantified. Most vulnerable components of the implemented circuit in terms of reliability are identified. Security is another major address of this work, since most current implementations include cryptographic devices. Fault-based attacks on such systems are known to be able to extract the secret key in feasible time. The remaining part of this work addresses such fault injection-based malicious attacks. Countermeasures based on a combination of information and hardware redundancy are considered. Recently introduced robust codes target such attacks by providing guaranteed detection capability. The performance of these codes is assessed by application to actual cryptographic and general purpose circuits. The work introduces metrics that help to identify fault locations in the circuit which could escape detection with high probability. These locations are targeted by transistor resizing that renders fault injection unfeasible.}, subject = {MIMO}, language = {en} } @phdthesis{Woelfl2018, author = {W{\"o}lfl, Andreas}, title = {Data Management in Certified Avionics Systems}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-5758}, school = {Universit{\"a}t Passau}, pages = {xi, 177 Seiten}, year = {2018}, abstract = {Data management is a cornerstone for any kind of information system - including the aerospace and aviation sector. In contrast to conventional domains, software development in the avionics domain must adhere to a legally binding certification process, called qualification. The success of the process depends on compliance with international standards, such as DO-178: Software Considerations in Airborne Systems and Equipment Certification. From a software developer's perspective, challenges arise in terms of methods and tools. Techniques that have a potential impact on the deterministic and predictable execution of avionics software are prohibited. The objective of this thesis' research is to develop a scalable method to realize data-management for multi-variant avionics software under the restrictions and constraints of the domain. Since avionics software faces very long-term life-cycles (up to 75 years), a particular focus is being placed on maintenance and evolution. Based on the insights gained in a semi-structured interview at Airbus Helicopters, industrial established approaches to implement qualified avionics software are assessed at first and compared with respect to strengths and weaknesses for data-management afterwards. As a result, a novel development approach is proposed, combining model-based techniques and product-line technology to derive the source code of highly specific data-management variants, as well as the majority of assets required for the qualification process, from a declarative system specification. In order to demonstrate the practicability of the approach in industry, a framework is presented that is deployed and applied at Airbus Helicopters to generate qualifiable data-management components for the variants of the NH90 helicopter. The maintainability is shown by means of a domain-specific optimization, in which the model-based and generative approach is used to establish safe memory overlays at compile-time. Key findings reveal a substantially reduced memory footprint (29,1\% in case of a real-world scenario), as well as an significantly facilitated implementation process, which would not be accomplishable using conventional methods for software development in the avionics domain.}, subject = {Avionik}, language = {en} } @phdthesis{Jovanovic2015, author = {Jovanovic, Philipp}, title = {Analysis and Design of Symmetric Cryptographic Algorithms}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-3319}, school = {Universit{\"a}t Passau}, pages = {216}, year = {2015}, abstract = {This doctoral thesis is dedicated to the analysis and the design of symmetric cryptographic algorithms. In the first part of the dissertation, we deal with fault-based attacks on cryptographic circuits which belong to the field of active implementation attacks and aim to retrieve secret keys stored on such chips. Our main focus lies on the cryptanalytic aspects of those attacks. In particular, we target block ciphers with a lightweight and (often) non-bijective key schedule where the derived subkeys are (almost) independent from each other. An attacker who is able to reconstruct one of the subkeys is thus not necessarily able to directly retrieve other subkeys or even the secret master key by simply reversing the key schedule. We introduce a framework based on differential fault analysis that allows to attack block ciphers with an arbitrary number of independent subkeys and which rely on a substitution-permutation network. These methods are then applied to the lightweight block ciphers LED and PRINCE and we show in both cases how to recover the secret master key requiring only a small number of fault injections. Moreover, we investigate approaches that utilize algebraic instead of differential techniques for the fault analysis and discuss advantages and drawbacks. At the end of the first part of the dissertation, we explore fault-based attacks on the block cipher Bel-T which also has a lightweight key schedule but is not based on a substitution-permutation network but instead on the so-called Lai-Massey scheme. The framework mentioned above is thus not usable against Bel-T. Nevertheless, we also present techniques for the case of Bel-T that enable full recovery of the secret key in a very efficient way using differential fault analysis. In the second part of the thesis, we focus on authenticated encryption schemes. While regular ciphers only protect privacy of processed data, authenticated encryption schemes also secure its authenticity and integrity. Many of these ciphers are additionally able to protect authenticity and integrity of so-called associated data. This type of data is transmitted unencrypted but nevertheless must be protected from being tampered with during transmission. Authenticated encryption is nowadays the standard technique to protect in-transit data. However, most of the currently deployed schemes have deficits and there are many leverage points for improvements. With NORX we introduce a novel authenticated encryption scheme supporting associated data. This algorithm was designed with high security, efficiency in both hardware and software, simplicity, and robustness against side-channel attacks in mind. Next to its specification, we present special features, security goals, implementation details, extensive performance measurements and discuss advantages over currently deployed standards. Finally, we describe our preliminary security analysis where we investigate differential and rotational properties of NORX. Noteworthy are in particular the newly developed techniques for differential cryptanalysis of NORX which exploit the power of SAT- and SMT-solvers and have the potential to be easily adaptable to other encryption schemes as well.}, subject = {Kryptologie}, language = {en} } @phdthesis{Ruppert2017, author = {Ruppert, Julia}, title = {Asymptotic Expansion for the Time Evolution of the Probability Distribution Given by the Brownian Motion on Semialgebraic Sets}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-5069}, school = {Universit{\"a}t Passau}, pages = {vi, 174 S.}, year = {2017}, abstract = {In this thesis, we examine whether the probability distribution given by the Brownian Motion on a semialgebraic set is definable in an o-minimal structure and we establish asymptotic expansions for the time evolution. We study the probability distribution as an example for the occurrence of special parameterized integrals of a globally subanalytic function and the exponential function of a globally subanalytic function. This work is motivated by the work of Comte, Lion and Rolin, which considered parameterized integrals of globally subanalytic functions, of Cluckers and Miller, which examined parameterized integrals of constructible functions, and by the work of Cluckers, Comte, Miller, Rolin and Servi, which treated oscillatory integrals of globally subanalytic functions. In the one dimensional case we show that the probability distribution on a family of sets, which are definable in an o-minimal structure, are definable in the Pfaffian closure. In the two-dimensional case we investigate asymptotic expansions for the time evolution. As time t approaches zero, we show that the integrals behave like a Puiseux series, which is not necessarily convergent. As t tends towards infinity, we show that the probability distribution is definable in the expansion of the real ordered field by all restricted analytic functions if the semialgebraic set is bounded. For this purpose, we apply results for parameterized integrals of globally subanalytic functions of Lion and Rolin. By establishing the asymptotic expansion of the integrals over an unbounded set, we demonstrate that this expansion has the form of convergent Puiseux series with negative exponents and their logarithm. Subsequently, we get that the asymptotic expansion is definable in an o-minimal structure. Finally, we study the three-dimensional case and give the proof that the probability distribution given by the Brownian Motion behaves like a Puiseux series as time t tends towards zero. As t approaches infinity and the semialgebraic set is bounded, it can be ascertained that the probability distribution has the form of a constructible function by results of Cluckers and Miller and therefore it is definable in an o-minimal structure. If the semialgebraic set is unbounded, we establish the asymptotic expansions and prove that the probability distribution given by the Brownian Motion on unbounded sets has an asymptotic expansion of the form of a constructible function. In consequence of that, the asymptotic expansion is definable in an o-minimal structure.}, subject = {Brownsche Bewegung}, language = {en} } @phdthesis{Boshe2017, author = {Boshe, Patricia}, title = {Data Protection Legal Reforms in Africa}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-5147}, school = {Universit{\"a}t Passau}, pages = {xxii, 141 Seiten}, year = {2017}, abstract = {This work illustrates reform approaches in Africa using an international legal comparative approach. The research uses Tanzania and Senegal as the primary case studies and France, the United Kingdom and Germany as secondary case studies to illustrate how Europe reformed data protection regimes through the transposition of the EU Data Protection Directive of 1995. Chapter one introduces the work; explaining the forces towards data protection regulations and their basis. Chapter two provides for a 'back-to-back' comparison in three countries (France, Germany and United Kingdom) against the 1995 Data Protection Directive. The idea behind this chapter is to draw a picture on how the legal culture and the pre-existing notions of the right to privacy inform on data protection legal reforms and determines the nature, contents, context and interpretation of adopted regime for data protection. Eventually, all these aspects affect the nature and extent of protection offered regardless of the substance of the law adopted. Chapter three gives a narrative explanation of nature and perceptions of the right to privacy in Africa and how this may affect data protection reforms in Africa. In the same disposition, African customary legal systems and practices are explained providing a reader with a picture of the overall nature of African systems that makes up an African legal culture. The overview of African privacy perception and legal system is necessary for assessing the workability of any data protection regime to be adopted in Africa which in effect answers the first research question. The chapter draws its rationale from chapter two. In understanding African perceptions of privacy and the African legal culture, one can be able to predict the content and context of the reforms and maybe how the judiciary might interpret the laws based on local perceptions and supporting systems. An overview of the African data protection architecture or rather human right architecture is provided in chapter four; ideally to provide a reader with a picture of the enforcement systems in Africa as a continent. This is followed by chapter five discussing the two major legal systems in Africa; the civil law and the common law system. The chapter also illustrates the position of African landscape in relation to legal harmonization/unification. This aspect is considered necessary because data protection regimes are more focused on legal harmonization and hence the question of how well or to what extent Africa as a continent can bring about harmonization in law became inevitable. Eventually, the chapter offers a comparative mirror analysis of the primary case studies, i.e. Senegal and Tanzania. The analysis is made on the reform approach taken, motivation behind the reforms and on the regime erected (this is done through textual analysis of the law and the draft bill respectively). Chapter six concludes the work by answering research questions based on findings and scrutiny from each chapter. It is concluded that there is a very slim chance for the African States to cling on the cultural defence against the adoption of the Western frameworks for data protection. It is also concluded that, lest Africa becomes an active participant in the global process that informs on data protection challenges and regulations, it faces a danger of becoming a puppet of foreign data protection regulation, which may or may not fit African legal culture. The chapter also illustrates how Africa as a continent and the African States individually have taken up data protection reforms blindly. The motivations for the reforms are vaguely stated and unclear. In the majority of legal instruments, the reforms are not taken as a move towards securing and protecting individual rights rather a purely political move influenced by economic motivations. The reforms are to a large extent, a mere impression to align with global data protection regimes and hence lack the political will to enforce the laws.}, subject = {African Privacy}, language = {en} } @phdthesis{Reislhuber2017, author = {Reislhuber, Josef}, title = {Optical Graph Recognition}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-5159}, school = {Universit{\"a}t Passau}, pages = {270 Seiten}, year = {2017}, abstract = {Graphs are an important model for the representation of structural information between objects. One identifies objects and nodes as well as a binary relation between objects and edges. Graphs have many uses, e. g., in social sciences, life sciences and engineering. There are two primary representations: abstract and visual. The abstract representation is well suited for processing graphs by computers and is given by an adjacency list, an adjacency matrix or any abstract data structure. A visual representation is used by human users who prefer a picture. Common terms are diagram, scheme, plan, or network. The objective of Graph Drawing is to transform a graph into a visual representation called the drawing of a graph. The goal is a "nice" drawing. In this thesis we introduce Optical Graph Recognition. Optical Graph Recognition (OGR) reverses Graph Drawing and transforms a digital image of a graph into an abstract representation. Our approach consists of four phases: Preprocessing where we determine which pixels of an image are part of the graph, Segmentation where we recognize the nodes, Topology Recognition where we detect the edges and Postprocessing where we enrich the recognized graph with additional information. We apply established digital image processing methods and make use of the special property that the image contains nodes that are connected by edges. We have focused on developing algorithms that need as little parameters as possible or to automatically calibrate the parameters. Most false recognition results are caused by crossing edges as this makes tracing the edges difficult and can lead to other recognition errors. We have evaluated hand-drawn and computer-drawn graphs. Our algorithms have a very high recognition rate for computer-drawn graphs, e. g., from a set of 100000 computer-drawn graphs over 90\% were correctly recognized. Most false recognition results where observed for hand-drawn graphs as they can include drawing errors and inaccuracies. For universal usability we have implemented a prototype called OGRup for mobile devices like smartphones or tablet computers. With our software it is possible to directly take a picture of a graph via a built in camera, recognize the graph, and then use the result for further processing. Furthermore, in order to gain more insight into the way a person draws a graph by hand, we have conducted a field study.}, subject = {Bildverarbeitung}, language = {en} } @phdthesis{dePonteMueller2016, author = {de Ponte M{\"u}ller, Fabian}, title = {Cooperative Relative Positioning for Vehicular Environments}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-5411}, school = {Universit{\"a}t Passau}, pages = {vii, 247 Seiten}, year = {2016}, abstract = {Fahrerassistenzsysteme sind ein wesentlicher Baustein zur Steigerung der Sicherheit im Straßenverkehr. Vor allem sicherheitsrelevante Applikationen ben{\"o}tigen eine genaue Information {\"u}ber den Ort und der Geschwindigkeit der Fahrzeuge in der unmittelbaren Umgebung, um m{\"o}gliche Gefahrensituationen vorherzusehen, den Fahrer zu warnen oder eigenst{\"a}ndig einzugreifen. Repr{\"a}sentative Beispiele f{\"u}r Assistenzsysteme, die auf eine genaue, kontinuierliche und zuverl{\"a}ssige Relativpositionierung anderer Verkehrsteilnehmer angewiesen sind, sind Notbremsassitenten, Spurwechselassitenten und Abstandsregeltempomate. Moderne L{\"o}sungsans{\"a}tze benutzen Umfeldsensorik wie zum Beispiel Radar, Laser Scanner oder Kameras, um die Position benachbarter Fahrzeuge zu sch{\"a}tzen. Dieser Sensorsysteme gemeinsame Nachteile sind deren limitierte Erfassungsreichweite und die Notwendigkeit einer direkten und nicht blockierten Sichtlinie zum Nachbarfahrzeug. Kooperative L{\"o}sungen basierend auf einer Fahrzeug-zu-Fahrzeug Kommunikation k{\"o}nnen die eigene Wahrnehmungsreichweite erh{\"o}hen, in dem Positionsinformationen zwischen den Verkehrsteilnehmern ausgetauscht werden. In dieser Dissertation soll die M{\"o}glichkeit der kooperativen Relativpositionierung von Straßenfahrzeugen mittels Fahrzeug-zu-Fahrzeug Kommunikation auf ihre Genauigkeit, Kontinuit{\"a}t und Robustheit untersucht werden. Anstatt die in jedem Fahrzeug unabh{\"a}ngig ermittelte Position zu {\"u}bertragen, werden in einem neuartigem Ansatz GNSS-Rohdaten, wie Pseudoranges und Doppler-Messungen, ausgetauscht. Dies hat den Vorteil, dass sich korrelierte Fehler in beiden Fahrzeugen potentiell herausk{\"u}rzen. Dies wird in dieser Dissertation mathematisch untersucht, simulativ modelliert und experimentell verifiziert. Um die Zuverl{\"a}ssigkeit und Kontinuit{\"a}t auch in "gest{\"o}rten" Umgebungen zu erh{\"o}hen, werden in einem Bayesischen Filter die GNSS-Rohdaten mit Inertialsensormessungen aus zwei Fahrzeugen fusioniert. Die Validierung des Sensorfusionsansatzes wurde im Rahmen dieser Dissertation in einem Verkehrs- sowie in einem GNSS-Simulator durchgef{\"u}hrt. Zur experimentellen Untersuchung wurden zwei Testfahrzeuge mit den verschiedenen Sensoren ausgestattet und Messungen in diversen Umgebungen gefahren. In dieser Arbeit wird gezeigt, dass auf Autobahnen, die Relativposition eines anderen Fahrzeugs mit einer Genauigkeit von unter einem Meter kontinuierlich gesch{\"a}tzt werden kann. Eine hohe Zuverl{\"a}ssigkeit in der longitudinalen und lateralen Richtung k{\"o}nnen erzielt werden und das System erweist 90\% der Zeit eine Unsicherheit unter 2.5m. In l{\"a}ndlichen Umgebungen w{\"a}chst die Unsicherheit in der relativen Position. Mit Hilfe der on-board Sensoren k{\"o}nnen Fehler bei der Fahrt durch W{\"a}lder und D{\"o}rfer korrekt gest{\"u}tzt werden. In st{\"a}dtischen Umgebungen werden die Limitierungen des Systems deutlich. Durch die erschwerte Sch{\"a}tzung der Fahrtrichtung des Ego-Fahrzeugs ist vor Allem die longitudinale Komponente der Relativen Position in st{\"a}dtischen Umgebungen stark verf{\"a}lscht.}, subject = {Fahrerassistenzsystem}, language = {en} } @phdthesis{Hanauer2018, author = {Hanauer, Kathrin}, title = {Linear Orderings of Sparse Graphs}, url = {http://nbn-resolving.de/urn:nbn:de:bvb:739-opus4-5524}, school = {Universit{\"a}t Passau}, pages = {vii, 282 Seiten}, year = {2018}, abstract = {The Linear Ordering problem consists in finding a total ordering of the vertices of a directed graph such that the number of backward arcs, i.e., arcs whose heads precede their tails in the ordering, is minimized. A minimum set of backward arcs corresponds to an optimal solution to the equivalent Feedback Arc Set problem and forms a minimum Cycle Cover. Linear Ordering and Feedback Arc Set are classic NP-hard optimization problems and have a wide range of applications. Whereas both problems have been studied intensively on dense graphs and tournaments, not much is known about their structure and properties on sparser graphs. There are also only few approximative algorithms that give performance guarantees especially for graphs with bounded vertex degree. This thesis fills this gap in multiple respects: We establish necessary conditions for a linear ordering (and thereby also for a feedback arc set) to be optimal, which provide new and fine-grained insights into the combinatorial structure of the problem. From these, we derive a framework for polynomial-time algorithms that construct linear orderings which adhere to one or more of these conditions. The analysis of the linear orderings produced by these algorithms is especially tailored to graphs with bounded vertex degrees of three and four and improves on previously known upper bounds. Furthermore, the set of necessary conditions is used to implement exact and fast algorithms for the Linear Ordering problem on sparse graphs. In an experimental evaluation, we finally show that the property-enforcing algorithms produce linear orderings that are very close to the optimum and that the exact representative delivers solutions in a timely manner also in practice. As an additional benefit, our results can be applied to the Acyclic Subgraph problem, which is the complementary problem to Feedback Arc Set, and provide insights into the dual problem of Feedback Arc Set, the Arc-Disjoint Cycles problem.}, subject = {Graphentheorie}, language = {en} }