| The field of computational complexity was born in the mid 1960s. Since then, many combinatorial problems have been classified in terms of the complexity classes to which they belong. This field has been one of the most recent successful areas in applied mathematics. On the other hand, despite these efforts, the classification of some problems remains open, and it is not known whether they are in P or NPC.; In this thesis, we prove the following properties concerning NP-completeness, approximability and performance guarantee for three combinatorial problems, each of which was not previously known. (1) The Planar Separator Problems. (1-1) NP-completeness of the Planar Vertex Separator Problem. (1-2) Existence of an O((|V(G) log |V( G)|)2/3)-approximation for the Graph Bisection problem. (2) The Variable Length Sequencing Problem (VLSP). (2-1) MAX-SNP hardness of VLSP with two lengths 1 and 3. (2-2) Existence of an Improved Approximation. (3) The Online Postman Problems. (3-1) Existence of an algorithm for a variant of the problem, with performance guarantee 2| V(G)| − 2. (3-2) Some lower bounds on a performance guarantee for the online postman algorithm. |
