Combinatorial Algorithms

Name: Combinatorial Algorithms | 21st International Workshop, IWOCA 2010, London, UK, July 26-28, 2010, Revised Selected Papers
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

21st International Workshop, IWOCA 2010, London, UK, July 26-28, 2010, Revised Selected Papers

Costas S. Iliopoulos William F. Smyth(Editor)

Springer (Publisher)

Published on 14. March 2011

XI, 418 pages

E-Book

PDF with digital watermarking

System requirements

978-3-642-19222-7 (ISBN)

€53.49incl. 7% vat

System requirements

for PDF with digital watermarking

E-Book Single Licence

Available for download

Description

More details

Other editions

Content

Title Page
Preface
Organization
Table of Contents
Parameterized Algorithms for the Independent Set Problem in Some Hereditary Graph Classes
Introduction
The Augmenting Graph Technique
Modular Decomposition
Concluding Remarks and Open Problems
References
On the Maximal Sum of Exponents of Runs in a String
Introduction
Preliminaries
Upper Bounds for s(n) and scubic(n)
Lower Bound for s(n)
Relating the Upper Bound for s(n) to Semicubic Runs
Conclusions
References
Path-Based Supports for Hypergraphs
Introduction
Preliminaries
Minimum and Planar Path-Based Supports
Path-Based Tree Supports
Constructing a Tree Support from the Hasse Diagram
Choosing the Connections: A Characterization
Conflict Computation and Run Time
Conclusion
References
On Improved Exact Algorithms for $L$(2, 1)-Labeling of Graphs
Introduction
Preliminaries
Improved Exact Algorithm for $L$(2,1) - Labeling
Generating 2-Packings
Improved Algorithm
References
Thread Graphs, Linear Rank-Width and Their Algorithmic Applications
Introduction
Linear Rank-Width
Thread Graphs
Algorithms on Thread Graphs
Computing Bandwidth
Dominating Bandwidth
The Path-Width Problem
Conclusion
References
Minimum Number of Holes in Unavoidable Sets of Partial Words of Size Three
Introduction
Preliminaries
Minimum Number of Holes in Unavoidable Sets
The C-Sets
The D-Sets
Proof of Our Main Result
References
Shortest Paths between Shortest Paths and Independent Sets
Introduction
Shortest Path Reconfiguration
Instances with Exponential Diameter
NP-Hardness of Min-SPR
Independent Set Reconfiguration: The Models
Hardness of Independent Set Reconfiguration
Positive Results for Independent Set Reconfiguration
Even-Hole-Free Graphs in the TJ Model
P4-Free Graphs in the TS Model
Concluding Remarks
References
Faster Bit-Parallel Algorithms for Unordered Pseudo-tree Matching and Tree Homeomorphism
Introduction
Preliminaries
Unordered Trees
Unordered Tree Matching Problem
Faster Bit-Parallel Algorithm for Unordered Pseudo tree Matching
Decomposition Formula and a Bottom-Up Algorithm
Bit-Parallel Implementation: Overview
Construction of a Monotone Bit-Assignment and an Overlap-Free Decomposition Based on Separator Trees
Complexity Analysis
Extension for Unordered Tree Homeomorphism
Conclusion
References
Dichotomy for Coloring of Dart Graphs
Introduction
Definitions
Properties of Dart Graphs
An Extension of Brooks Theorem
NP-Completeness
References
Worst Case Efficient Single and Multiple String Matching in the RAM Model
Introduction
Outline of the Results
Problem Definition, Notation and Preliminaries
Results
Multiple String Matching without Tabulation
Components
Overview
The Data Structure
Simulating Transitions
Identifying Matching Occurrences
Tabulation Based Solution
Conclusion
References
The (2,1)-Total Labeling Number of Outerplanar Graphs Is at Most ? + 2
Introduction
The Main Theorem
Proof Sketch of Theorem
References
Upper and Lower I/O Bounds for Pebbling r-Pyramids
Introduction
Background
Computation Graphs, Structures and Memory Traffic Complexity
The Reb-Blue Pebble Game
An Efficient Algorithm for Pebbling Pr(n)
An r-Pyramid
Algorithm
Lower Bounds for Pebbling an r-Pyramid
A Lower Bound Based on the S-Span of a Graph
The Blue Pebble Strategy for Proving Pebbling Lower Bounds
A Lower Bound for Pebbling $P_r(n)$
Remarks and Conclusion
References
Single Parameter FPT-Algorithms for Non-trivial Games
Introduction
FPT Results for Win-Lose Games
FPT Results When Searching Nash Equilibrium on a Set
FPT Results for Congestion Games
References
The Complexity Status of Problems Related to Sparsest Cuts
Introduction
NP-Completeness of the Densest Cut Problem
The Case of Bounded Treewidth
Conclusions
References
On Approximation Complexity of Metric Dimension Problem
Introduction
Related Work
Our Contributions
References
Collision-Free Routing in Sink-Centric Sensor Networks with Coarse-Grain Coordinates
Introduction
Outline
The Model
Localization
Coloring
Algorithm $Col$4
Algorithm $Col$3
Leader Election and Routing
Conclusions
References
Complexity of Most Vital Nodes for Independent Set in Graphs Related to Tree Structures
Introduction
Preliminaries
Complexity on Bipartite Graphs
Graph Classes Related to Tree Structures
Trees
Cycles
Graphs of Bounded Treewidth
Cographs
Conclusion
References
Computing Role Assignments of Proper Interval Graphs in Polynomial Time
Introduction
Preliminaries
Chordal, Interval, and Proper Interval Graphs
Role Assignments
Role Assignments on Proper Interval Graphs
Complementary Results and an Open Question
References
Efficient Connectivity Testing of Hypercubic Networks with Faults
Introduction
Preliminaries
Expansion Approach
Transformations of Walks in Hypercubes
Local Connectivity
Algorithm
Concluding Remarks
References
Reductions of Matrices Associated with Nowhere-Zero Flows
Introduction
Preliminaries
Forbidden Networks
Superproper Permutations
?n-Classes
Excluding Girth Seven
Computations
References
Blocks of Hypergraphs Applied to Hypergraphs and Outerplanarity
Introduction
Biconnected Components
Cactus Supports
Hypergraphs Closed under Intersections and Differences
Conclusions
References
Testing the Simultaneous Embeddability of Two Graphs Whose Intersection Is a Biconnected Graph or a Tree
Introduction
Preliminaries
The Intersection Graph Is Biconnected
The Intersection Graph Is a Tree
Conclusions
References
Skip Lift: A Probabilistic Alternative to Red-Black Trees
Introduction
Skip List
Related Work
Skip Lift
Finger Search
Overview of Randomized Dictionaries
Modified Skip List
Treap
Randomized Binary Search Tree
Jumplist
References
On a Relationship between Completely Separating Systems and Antimagic Labeling of Regular Graphs
Introduction
Results
Conclusion
References
Parameterized Complexity of $k$-Anonymity: Hardness and Tractability
Introduction
Preliminary Definitions
&e&-AP and &e, k&-AP Are W[1]-Hard
An FPT Algorithm for &|S|,m&-AP
Building the Graph $G_R,S'$
Computing a Solution of &|S|,m&-AP
Proving the Optimality of $?S (M)$
Conclusions
References
On Fast Enumeration of Pseudo Bicliques
Introduction
Pseudo Biclique Generation Algorithm
Computational Results
References
Efficient Chaining of Seeds in Ordered Trees
Introduction
Background and Problem Statement
Combinatorial Properties of Seeds and Chains
Algorithms for the Maximum Chaining Problem
A Simple Non Optimal Algorithm
A More Efficient Algorithm
Conclusion
References
On the Computational Complexity of Degenerate Unit Distance Representations of Graphs
Introduction and Background
Notation
Unit Distance Representations
PSPACE Membership
2-Dimensional Unit Distance Representations
$k$-Dimensional Unit Distance Representations
Conclusion
References
Recognition of Probe Ptolemaic Graphs
Introduction
A Recognition Algorithm
References
Graphs of Separability at Most Two: Structural Characterizations and Their Consequences
Introduction
A Structure Theorem for Graphs of Separability at Most Two
Algorithmic and Complexity Issues
Characterizations by Forbidden Substructures
Open Problems
References
On Antimagic Labeling for Generalized Web and Flower Graphs
Introduction
Results
References
Chains-into-Bins Processes
Introduction
Related Work
Model and Results
Analysis of GREEDY_CHAINS[$d, l$]
Allocating Chain Headers
Proof of Theorem
Proof of Theorem
Conclusions and Open Problems
References
Complexity of Locally Injective Homomorphism to the Theta Graphs
Introduction
Definitions and Gadgets
NP-Completeness Reductions
References
Ranking and Drawing in Subexponential Time
Introduction
Preliminaries
FPT Algorithms for $p$-KAGG
Parameterized Reduction from $p$-KAGG to $p$-WDFAS
A Subexponential FPT Algorithm for $p$-KAGG
FPT Algorithms for $A-p$-KAGG
A Lower Bound for $A-p$-KAGG($even$)
FPT Algorithms for $p$-OSCM
Parameterized Reduction from $p$-OSCM to $p$-WDFAS
A Subexponential FPT Algorithm for $p$-OSCM
Lower and Upper Bounds for $A-p$-OSCM
Conclusion and Future Work
References
Efficient Reconstruction of RC-Equivalent Strings
Introduction
Preliminaries
Unbounded Query Size
Bounded Query Size (Binary Alphabet)
The Case Where $A = T$
The Case $T &A&B$
The Case $T &A= B = n/2, s1 = s_n$
The Case $T &A= B = n/2, s1 = s_n$
References
Improved Points Approximation Algorithms Based on Simplicial Thickness Data Structures
Introduction
An Improved Algorithm for VWPF
Data Structure Based on Hierarchical Cuttings
High Dimensional Space (d&2)
Auxiliary Data Structure for the Planar Case
Data Structure Based on Simplicial Partitions
Handling the Weighted STQ and Max-STQ
References
The Cover Time of Cartesian Product Graphs
Introduction
Preliminaries
Some Notation
Blanket Time
Random Walks and Electrical Networks
Related Work
Locally Observed Random Walk
A General Bound
References
Dictionary-Symbolwise Flexible Parsing
Introduction
Preliminaries
On Optimality
Dictionary-Symbolwise Flexible Parsing Algorithm
Data Structures and Time Analysis
Conclusions
References
Regular Language Constrained Sequence Alignment Revisited
Introduction
Constrained Sequence Alignment
Preliminaries and Definitions
An Overview of Previous Work
A Faster Algorithm
Eliminating Duplicate Computations
An Algorithm Based on a Steiner Minimal Directed Tree
A Solution to Subsets Maxima via SLPs
Simulation Results
References
Author Index

System requirements

Save as PDF Copy link into clipboard

Schweitzer Fachinformationen

Combinatorial Algorithms

Description

More details

Other editions

Additional editions

Content

System requirements