Please use this identifier to cite or link to this item:

`http://hdl.handle.net/2381/30518`

Title: | The complexity of greedy algorithms on ordered graphs |

Authors: | Puricella, Antonio. |

Award date: | 2002 |

Presented at: | University of Leicester |

Abstract: | Let p be any fixed polynomial time testable, non-trivial, hereditary property of graphs. Suppose that the vertices of a graph G are not necessarily linearly ordered but partially ordered, where we think of this partial order as a collection of (possibly exponentially many) linear orders in the natural way. In the first part of this thesis, we prove that the problem of deciding whether a lexicographically first maximal (with respect to one of these linear orders) subgraph of G satisfying p, contains a specified vertex is NP-complete. For some of these properties p we then show that by applying certain restrictions the problem still remains NP-complete, and show how the problem can be solved in deterministic polynomial time if the restrictions imposed become more severe.;Let H be a fixed undirected graph. An H-colouring of an undirected graph G is a homomorphism from G to H. In the second part of the thesis, we show that, if the vertices of G are partially ordered then the complexity of deciding whether a given vertex of G is in a lexicographically first maximal H-colourable subgraph of G is NP-complete, if H is bipartite, and Sp2-complete, if H is non-bipartite. We then show that if the vertices of G are linearly, as opposed to partially, ordered then the complexity of deciding whether a given vertex of G is in the lexicographically first maximal H-colourable subgraph of G is P-complete, if H is bipartite, and DP2-complete, if H is non-bipartite.;In the final part of the thesis we show that the results obtained can be paralleled in the setting of graphs where orders are given by degrees of the vertices. |

Links: | http://hdl.handle.net/2381/30518 |

Type: | Thesis |

Level: | Doctoral |

Qualification: | PhD |

Rights: | Copyright © the author. All rights reserved. |

Appears in Collections: | Theses, Dept. of Mathematics Leicester Theses |

Files in This Item:

File | Description | Size | Format | |
---|---|---|---|---|

U153592.pdf | 4.58 MB | Adobe PDF | View/Open |

Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.