home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / theory / 2844 < prev    next >
Encoding:
Text File  |  1993-01-09  |  2.8 KB  |  75 lines
  1. Newsgroups: comp.theory
  2. Path: sparky!uunet!math.fu-berlin.de!informatik.tu-muenchen.de!rz.uni-passau.de!unipas.fmi.uni-passau.de!schweika
  3. From: schweika@unipas.fmi.uni-passau.de (Andreas Schweikardt)
  4. Subject: dynamic and static separators
  5. Message-ID: <1993Jan9.152621.18490@tom.rz.uni-passau.de>
  6. Sender: news@tom.rz.uni-passau.de (News-Operator)
  7. Organization: University of Passau, Germany
  8. Date: Sat, 9 Jan 1993 15:26:21 GMT
  9. Lines: 64
  10.  
  11. Hi,
  12.  
  13. I have a problem (and want it solved ;-)):
  14.  
  15. Does anyone know the relationship between the two versions of 
  16. graph separators ?
  17.  
  18. Keywords: separator, vertex separator, pathwidth, node search number
  19.  
  20. Thomas Lengauer described in his article "Black-White Pebbles and 
  21. Graph Separation" (Acta Informatica 16, 465-475 (1981))
  22. the well-known "static" version of graph separators and he introduced
  23. a "dynamic" version.
  24.  
  25. Can anyone give me a hint to the relation between the "dynamic" and the
  26. "static" separator ?
  27.  
  28. The static version:
  29.  
  30. An undirected graph G=(V,E) with n vertices has a f(n) separator iff
  31. V can be separated in three disjunct sets A, B and S, A and B have 
  32. no edges in common, (1/3)n <= #A <= (2/3)n, (1/3)n <= #B <= (2/3). 
  33. S contains no more than f(n) vertices. A and B have also a 
  34. f(n) separator (recursively applied on A and B).
  35.  
  36.  
  37. The dynamic version: 
  38.  
  39. I give here T. Lengauer's definition:
  40. "... The above definition of a separator is a 'static' one. We will here
  41. define a corresponding(*) 'dynamic' notion of a separator. The definition
  42. will be in terms of a pebble game on undirected graphs called the Vertex
  43. Separator Game (VSG).
  44. The VSG is played on undirected graphs G according to the following rules.
  45.  
  46. (i)   All vertices start out pebble-free.
  47. (ii)  All vertices end up pebbled.
  48. (iii) A move consists of placing a pebble on a pebble-free vertex.
  49.  
  50. The Vertex Cut after the i-th move consists of all vertices that are pebble-
  51. free and adjacent to a pebbled vertex after the i-th move. Let S be a
  52. strategy for VSG on G [G is the graph], i.e. a permutation of the vertices 
  53. of G that represents a sequence of moves (applications of rule (iii)) in
  54. VSG. ..."
  55. (*) Well, that's my problem "corresponding".
  56.  
  57. And the vertex cut of a strategy is the maximum vertex cut after every move.
  58. The dynamic or vertex separator is the minumum vertex cut of all strategies
  59. for the graph.
  60. Related graph theoretic topics are the node search number and pathwidth
  61. of an undirected graph. 
  62. That is  node search number -1 = pathwidth = dynamic separator.
  63.  
  64. Is it possible to transform a "static" to a "dynamic" separator and 
  65. vice versa ?
  66.  
  67. Please send any ideas or hints to my address. Thanks ! 
  68. Email-address: schweika@trillian.fmi.uni-passau.de
  69.  
  70. Thank you
  71.                 Andreas Schweikardt
  72. -- 
  73. Andreas Schweikardt * Ingling 17 * 4784 Schardenberg * Austria
  74.                     trillian@fmi.uni-passau.de    
  75.