Yearly Archives: 2000

I have been staying in Camerino, Italy for 3 months where I have visited professor Daniele Pretolani. During my stay, we developed procedures to solve the k’th shortest hyperpath problem and the bi-SBT problem. The k’th shortest hyperpath problem is solved using a new branching rule which divides the hypergraph into subhypergraphs. The bi-SBT problem is solved using different methods which are tested against each other (simple k’th method, two-phases method and k’th diagonal method). During my stay I also found a small error in the definition of a hyperpath which has been used in many papers. I therefore wrote a short note with a new definition (see publications).

I have started a project on bicriterion shortest hyperpaths (bi-SBT) together with my supervisor Kim Allan Andersen. This is a totally new research area, and we have to start from scratch by defining a bicriterion hypergraph and formulating the bi-SBT problem. First, I began studying the bicriterion shortest path problem and the methods to solve it. There are two main approaches, namely node labeling and path/tree. The node labeling approach seems to be hard to transfer to hypergraphs because a hyperpath has a more complex structure than a path, resulting in more complex node labeling procedure. Furthermore, an efficient path satisfies that its subpaths are efficient; this is not always the case for hyperpaths. The path/tree approach seems more adaptable to hypergraphs. Most papers use a k’th shortest path subprocedure to solve the problem. Therefore I first developed methods to solve the k’th shortest hyperpath problem. Conferences: “Probabilistic methods in […]