courcell@geocub.greco-prog.FR (Bruno Courcelle) (12/01/90)
Publication announcement MONADIC SECOND-ORDER EVALUATIONS ON TREE DECOMPOSABLE GRAPHS by B.COURCELLE, M. MOSBAH, Bordeaux -1 University, FRANCE Abstract: We consider mappings on weighted graphs , like minimal length of a Hamiltonian path or minimal weight of a spanning tree, or number of simple paths linking two designated vertices. Another case is the selection of an optimal subgraph as in Bern, Lawler and Wang. We express the mappings by monadic second-order logic: formulas describe sets of sets of vertices or edges satifying appropriate conditions. Then a semiring homomorphism can select the maximal cardinality, or weight, or the cardinality, etc... For all the problems expressible in this way we obtain polynomial and frequently linear algorithms for graphs given with a decomposition tree, or a parse-tree relative to a context-free graph grammar. We extend results by Arnborg Lagergren and Seese (ICALP 88) or Habel, Kreowski and Vogler ( TAPSOFT 89, LNCS 351), and we answer the questions raised in Bern et al.. This work is available as a printed report (51 pages : request to courcell@geocub.greco-prog.fr) or a LATEX file (request to mosbah@geocub.greco-prog.fr) Mailing address: Universite Bordeaux-1, Informatique, 351 Cours de la Liberation, 33405 TALENCE, France.
pcolsen@super.ORG (Peter C Olsen) (12/02/90)
Can anyone point me toward data for the Traveling Salesman problem with known solutions? I experimenting with some Neural Network approximations and I'd like some known standards against which to compare. Thanks. Peter Olsen, pcolsen@super.super.org