Lecture 6: List contraction, tree contraction, and symmetry breaking 1 Work-efficient list prefix

• Main Author: In The
• Other Authors: The Pennsylvania State University CiteSeerX Archives
• Format: Text
• Language: English
• Subjects: The Pointers
• Online Access: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.56.5126

ad or tail, and then picking any head-labeled element which is not followed immediately by a head-labeled element. (In this scheme, the last element of the list is always chosen if it is a head.) The victims form an independent set (that is, a subset of the graph in which no two nodes are adjacent), since if an element is a victim, its successor is a tail and its predecessor is followed by a head (the victim itself) and so neither neighbor can also be a victim. 2. Splice out victims. The victims are then spliced out of the list by jumping the pointers of their predecessors over them. As each victim i is removed from the list, its value a i is pushed into its successor by setting the successor's value to be a i\Omega a i+1 . (Independence of victims guarantees that the successor is not al