6533b7d7fe1ef96bd1268e16

RESEARCH PRODUCT

Algorithms on Graphs

Eljas Soisalon-soininenSeppo Sippu

subject

Modular decompositionIndifference graphPathwidthClique problemComputer scienceChordal graphDirected graphAlgorithmImplicit graphGraph product

description

In this chapter we shall develop some basic algorithms for directed graphs and relations which will be of use in later chapters, where the efficient construction of parsers is considered. The constructions needed can be expressed as the computing of certain “relational expressions”. These are expressions whose operands are relations and whose operators are chosen from among multiplication, closure, union and inverse. For this purpose we need to develop an algorithm for computing the closure of a relation. In view of the nature of our applications, the most appropriate way to do this is by a depth-first traversal of the graph that corresponds to the given relation. Other ways of computing the closure of a relation are considered in the exercises.

yearjournalcountryeditionlanguage
1988-01-01
https://doi.org/10.1007/978-3-642-61345-6_2