Applied graph algorithms

点击翻译按钮获取中文摘要

Algorithmic graph theory has numerous applications either directly in practice or in other research fields. In this project I propose to deal with some graph theory algorithmic problems arising mainly in the fields of computational geometry, formal languages and distributed computing.         Graph drawing is an important domain, related, besides computational geometry, to the fields of knowledge representation, graph theory, human cognition and many others. The fundamental question here is how to visualize a graph representing structural knowledge, so that a human confronted with this visualization will easily perceive some of its important properties, for example in order to make critical decisions fast. I would like to design the drawing algorithms for some classes of graphs.         A motion of polygonal objects in the plane may be represented by geometric graphs. Their mobility within the plane environment, without interfering with obstacles, was studied in robotics, motion planning and grasping. In order to immobilize a polygonal object, motionless obstacles are placed around its boundary, preventing any rigid movement. I propose to study optimal immobilizations of polygonal objects with a set of points, according to different criteria of optimality.         One of the approaches to data packet classification uses finite state automata. An automaton reads an input string and stops in the final state corresponding to the result of this classification. Several problems concerning such automata transform to graph-theoretical questions related to some classes of graphs. In my research, I will study some algorithms for this class of graphs, important in practice, since this portion of my project comes directly from an industrial application.         Several problems in distributed computing relate to graph investigation by use of sets of collaborating mobile agents, walking along the graph. I intend to study models of graph investigation by mobile agents for some classes of graphs.