Combinatorial Algorithms. 22nd International Workshop, IWOCA 2011 Vancouver, BC, Canada, July 20-22, 2011 Revised Selected Papers

Description

Cover Lecture Notes in Computer Science 7056 Combinatorial Algorithms ISBN 9783642250101 Preface Organization Table of Contents Weighted Improper Colouring Introduction General Results NP-Completeness of Threshold Improper colouring Bounds Transformation Squares of Particular Graphs Infinite Paths and Trees Grids Integer Programs, Algorithms and Results Integer Programs and Algorithms Results Conclusion, Open Problems and Future Directions References Algorithmic Aspects of Dominator Colorings in Graphs Introduction Preliminaries Hardness Results NP-Hardness of DC on Split Graphs Parameterized Algorithms Conclusion and Scope References Parameterized Longest Previous Factor Introduction Background / Related Work Preliminaries Parameterized LPF From pLPF to pLCP From pLPF to LPF and LCP Conclusion and Discussion References p-Suffix Sorting as Arithmetic Coding Introduction Background / Related Work Preliminaries p-Suffix Sorting via Fingerprints p-Suffix Sorting via Arithmetic Coding Conclusion and Discussion References Periods in Partial Words: An Algorithm Introduction ($p,q$ )-Periodic Graphs Connectivity in ($p, q$ )-Periodic Graphs $r$ -Set Connectivity Modified Degree Connectivity Conclusion References The 1-Neighbour Knapsack Problem Introduction The General 1-Neighbour Knapsack Problem The General, Undirected 1-Neighbour Problem General, Directed 1-Neighbour Knapsack Is Hard to Approximate The Uniform, Directed 1-Neighbour Knapsack Problem The Uniform, Undirected 1-Neighbour Problem References A Golden Ratio Parameterized Algorithm for Cluster Editing Introduction Preliminaries Vertex Parities Isolation and Vertices of Even Parity Solving Remainder Instances A Golden Ratio Base for Search Tree Size Conclusion References Stable Sets of Threshold-Based Cascades on the Erd˝os-R´enyi Random Graphs Introduction Definitions Stable Sets of the Erdős-Rényi Random Graphs References How Not to Characterize Planar-Emulable Graphs Introduction On Planar Covers and Emulators Basic Properties of Emulators Constructing New Planar Emulators Structural Search: How Far Can We Go? Conclusion and Further Questions References Testing Monotone Read-Once Functions Introduction Combinatorial Reduction Obtaining Bounds on $L(F)$ Conclusions References Complexity of Cycle Transverse Matching Problems Introduction TM($C_3$) and ST($C_3$ ) for Line Graphs are Polynomial TM($C_4$ ) is NP-Complete TM($C_l$) is NP-Complete for l ≥ 5 Conclusion and Further Remarks References Efficient Conditional Expectation Algorithms for Constructing Hash Families Introduction The Stein-Lovász-Johnson Paradigm Variants of Hash Families Constructing a Hash Family The Method of Conditional Expectations Conclusion References 2-Layer Right Angle Crossing Drawings Introduction Geometry and Combinatorics of 2-Layer RAC Drawings Characterization and Testing Algorithms Characterization of Biconnected Graphs Characterization of Trees Characterization of 2-Layer RAC Graphs Optimization Problems Open Problems References Hamiltonian Orthogeodesic Alternating Paths Introduction Preliminaries Hamiltonian Orthogeodesic Alternating Paths Hamiltonian Orthogeodesic Alternating Paths on the Grid Additional Results Open Problems References Ranking and Loopless Generation of k-ary Dyck Words in Cool-lex Order Background k-ary Dyck Words Combinatorial Generation CoolCat Order Bubble Languages and Cool-lex Order New Results CoolKat Order Optimized Swap Rules Loopless Algorithms Algorithm for Constant k Algorithm for Arbitrary k Ranking and Unranking References Two Constant-Factor-Optimal Realizations of Adaptive Heapsort Introduction Adaptive Heapsort Weak Heaps with Bulk Insertions Weak Queues with Bulk Insertions Experimental Findings Conclusions References A Unifying Property for Distribution-Sensitive Priority Queues Introduction From the Working-Set Bound to the Unified Bound A Priority Queue with the Working-Set Property Supporting $delete, find-min and decrease-key$ Incorporating the Queueish Property Supporting Multiple Time Fingers Conclusion References Enumerating Tatami Mat Arrangements of Square Grids Introduction Structure Square Grids Conclusions and Further Research References Quasi-Cyclic Codes over F13 Introduction Quasi-Cyclic Codes The Construction Algorithm References Acyclic Colorings of Graph Subdivisions Introduction Preliminaries Acyclic Coloring of Plane Graphs NP-Completeness Open Problems References Kinetic Euclidean Minimum Spanning Tree in the Plane Introduction Certificates and Events Building the Kinetic Data Structure Event Handling Processing DT-Events Processing Order Events Performance Analysis Conclusion References Generating All Simple Convexly-Drawable Polar Symmetric 6-Venn Diagrams Introduction Basic Definitions Representing Venn Diagrams Matrix Representation Compositions Generating Algorithm Results References The Rand and Block Distances of Pairs of Set Partitions Introduction and Motivation Background on Set Partitions The Block Distance Linear Time Algorithm to Compute the Block Distance Results on the Rand Distance Determining $R(n,k)$ for Small Values of $k$ The Numbers $R(n,n ()2-k) $for Small $k$ References On Minimizing the Number of Label Transitions around a Vertex of a Planar Graph Introduction Bounded Number of Labels Dealing with Bridge Vectors NP-Completeness References A New View on Rural Postman Based on Eulerian Extension and Matching Introduction Preliminaries and Preparations Preprocessing Routines Advice Eulerian Extension and Conjoining Bipartite Matching From Eulerian Extension to Matching From Matching to Eulerian Extension with Advice Removing Advice Conjoining Bipartite Matching: Properties and Special Cases NP-Hardness Tractability on Restricted Graph Classes Conclusion References Hamilton Cycles in Restricted Rotator Graphs Introduction Rotator Graphs and Hamilton Cycles New Results Sequence Building Reusing and Recycling Rotation Identities List Quotients Three Hamilton Sequences Hamilton Sequence for $R_n$ Hamilton Sequence for $R_n$ [n]{n - 1,n} Hamilton Sequence for $R_n$ [n]{2,3,n} Loopless Algorithm Staircase Sequence Staircase Strings Corbett's Successor Rule Recycling Corbett's Sequence Open Problems References Efficient Codon Optimization with Motif Engineering Introduction Preliminaries A DP Algorithm for CAI Optimization Empirical Results Results Conclusions References An Algorithm for Road Coloring Some Properties of F-Cliques and Stable Pairs The Spanning Subgraph of an AGW Graph The Algorithm for Synchronizing Coloring Preliminary Steps Help Subroutines A Possibility to Reduce the Complexity The Recoloring of the Edges Main Procedure and Complexity References Complexity of the Cop and Robber Guarding Game Introduction and Motivation The Directed Case The Variable Cells The Gates to $VC$ The Big Picture Further Questions and Acknowledgements References Improved Steiner Tree Algorithms for Bounded Treewidth Introduction Steiner Tree Algorithm Representing Sub-solutions Processing the Decomposition Tree Analysis Prize-Collecting Steiner Tree $k$ -Cardinality Tree Conclusions References Author Index