This thesis examines graph-theoretic approaches to problems arising in emitter- to-platform association, for example in associating emitters and ships. The first part of this thesis focuses on emitters that are observed by two different sensors, which can only determine the bearing the observed signal was emitted from. The aim is to pair observations from the two sensors, that originate from the same emitter. In this thesis it is shown that different types of observations can be represented as one of c colours and each observed bearing as a row or a column in an n by n grid. Given the horizontal and vertical projections of a coloured grid, the aim is to reconstruct the original layout of the coloured squares on the grid. Deciding whether two sets of positive natural numbers are the horizontal and vertical projections of a coloured grid is NP-complete for two or more colours [24, 35, 47] and has close connections to colour degree matrix problems. Necessary and sufficient conditions are known for a demand matrix to be a colour degree matrix of an edge-coloured forest [9, 22]. In this thesis the first step beyond forests is taken: necessary and sufficient conditions for a demand matrix to be realisable by a graph with at most one cycle are proved. As part of the proof some directly forced structures are discovered, that is, structures that must exist in every realisation. Moreover, corresponding results for multi-graphs and pseudoforests with at most k cyclic components are presented. This part concludes with O (n2 ) time algorithms to check these conditions and return a witness if one of the conditions is violated. Finally O(n3) time algorithms to find a realisation, if one exists, are described. The second part of this thesis introduces the coloured L-model. This is an original idealised graph model, developed to explore the combinatorial properties of the emitter-to-platform association problem, referred to as the reverse radar problem in this thesis. The aim is to decide which groups of observed radars originate from the same ship, taking into account which combinations of radar models are known to be carried by different types of ships. It is shown what exactly makes finding a solution to this idealised version of the reverse radar problem NP-hard, and that there are tractable cases equivalent to finding (weighted) matchings in related graphs, which have bounded pathwidth. Restricting to graphs with bounded pathwidth is a reasonable simplification, as signals come in along bearings (i.e. along a cycle) and a cycle has pathwidth two. New algorithms to find (weighted) matchings in graphs with bounded pathwidth and treewidth are presented, which can be used to solve the reverse radar problem in this model. Finally, the likelihood and two-time models are introduced, which complement the coloured L-model by generalising measurement errors and by introducing time. It is shown that the problem remains NP-hard, even for very simple cases and some tractable cases are described.
| Identifer | oai:union.ndltd.org:bl.uk/oai:ethos.bl.uk:713950 |
| Date | January 2015 |
| Creators | Hillebrand, Anne |
| Contributors | McDiarmid, Colin ; Scott, Alexander |
| Publisher | University of Oxford |
| Source Sets | Ethos UK |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
| Source | https://ora.ox.ac.uk/objects/uuid:54e2170e-ec6b-4bdc-886f-d9bc1468fce8 |
Page generated in 0.0022 seconds