Language Constrained Graph Problems A Microcosm of Engineering Research and Development (Plenary Talk)

摘要

This paper starts by discussing an algorithmic view of labeled path problems. In particular, we apply Seidel's all-pairs shortest-path algorithm for undirected and un-weighted graphs to a basic problem in labeled paths. Seidel's algorithm is applied to find unlabeled paths between any pairs of nodes in a labeled graph whose associated context-free grammar G can generate the empty string ∈. Our result is a corollary of Seidel's algorithm. Then we mention a number of diverse labeled path applications. Labeled path problems are then used to demonstrate some concepts and insights about research and development. We briefly discuss their place in building our intellectual infrastructure as well as their potential contributions to modern business and entrepreneurship. We attempt to give a broad perspective to research and development from their intellectual foundations to their place in modern business and entrepreneurship. It serves as a high-level sketch rather than a comprehensive discussion.