Combinatorial Algorithms
22th International Workshop, IWOCA 2011, Victoria, Canada, July 20-22, 2011, Revised Selected Papers
Published on 10. November 2011
XI, 387 pages
978-3-642-25011-8 (ISBN)
Description
This book constitutes the thoroughly referred post-workshop proceedings of the 22nd International Workshop on Combinatorial Algorithms, IWOCA 2011, held in Victoria, BC, Canada, in July 2011. The 30 revised full papers presented were carefully reviewed and selected from a total of 71 submissions. A broad variety of topics in combinatorics and graph theory are addressed, such as combinatorics on words, string algorithms, codes, Venn diagrams, set partitions; Hamiltonian & Eulerian properties, graph drawing, colouring, dominating sets, spanning trees, and others.
More details
Other editions
Additional editions
Costas S. Iliopoulos | William F. Smyth
Combinatorial Algorithms
22th International Workshop, IWOCA 2011, Victoria, Canada, July 20-22, 2011, Revised Selected Papers
Book
01/2012
Springer
€53.49
Shipment within 7-9 days
Content
- Intro
- Title page
- 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 Erdos-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 $F_13$
- 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 Rn
- Hamilton Sequence for [n]{n-1,n}
- Hamilton Sequence for [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
