Computing and Combinatorics

Name: Computing and Combinatorics | 17th Annual International Conference, COCOON 2011, Dallas, TX, USA, August 14-16, 2011. Proceedings
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

17th Annual International Conference, COCOON 2011, Dallas, TX, USA, August 14-16, 2011. Proceedings

Bin Fu Ding-Zhu Du(Herausgeber*in)

Springer (Verlag)

Erschienen am 18. Juli 2011

XIII, 650 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-642-22685-4 (ISBN)

53,49 €inkl. 7% MwSt.

Systemvoraussetzungen

für PDF mit Wasserzeichen-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

Weitere Details

Weitere Ausgaben

Inhalt

Title
Preface
Organization
Table of Contents
Derandomizing HSSW Algorithm for 3-SAT
Introduction
Preliminaries
A Derandomization of HSSW
Conclusion
References
Dominating Set Counting in Graph Classes
Introduction
Interval Graphs
Counting the Dominating Sets
Speeding Up the Dynamic Programming
Counting the Minimum Dominating Sets
Split Graphs
Cobipartite Graphs
Chordal Bipartite Graphs
Concluding Remarks
References
The Density Maximization Problem in Graphs
Introduction
Bi-constrained Maximum Density Subgraph
An FPTAS for Relaxed Density Maximization
Conclusion and Outlook
References
FlipCut Supertrees: Towards Matrix Representation Accuracy in Polynomial Time
Introduction
Preliminaries
The FlipCut Algorithm
Using Branch Lengths
The Undisputed Sibling Problem
Experiments
Results
Conclusion
References
Tight Bounds on Local Search to Approximate the Maximum Satisfiability Problems
Introduction
Local Search for Max-(2)-Sat
The 4/3-Approximation Algorithm for Max-E2-Sat
On the General Case of Max-(k)-Sat
The 8/7-Approximation Algorithm for Max-(3)-Sat
The 8/7-Approximation Algorithm for Max-E3-Sat
On the General Case of Max-(k)-Sat
Local Search for Other Variants
Conclusion
References
Parameterized Complexity in Multiple-Interval Graphs: Partition, Separation, Irredundancy
Introduction
Preliminaries
Vertex Clique Partition
Separating Vertices
Irredundant Set
References
Exact Parameterized Multilinear Monomial Counting via k-Layer Subset Convolution and k-Disjoint Sum
Introduction
Related Work
Preliminaries
Zeta Transform and Möbius Inversion
Subset Convolution
Faster Algorithms for Exact Multilinear k-Monomial Counting
k-Disjoint Sum
Algorithms for Exact Multilinear k-Monomial Counting
A Polynomial Space Algorithm for Exact Multilinear k-Monomial Counting
Applications
#k-Path
#m-Set k-Packing
Conclusions
References
On the Rainbow Connectivity of Graphs: Complexity and FPT Algorithms
Introduction
Complexity for Edge-Coloring Version
Strong NP-Completeness for Outerplanar Graphs
Polynomial-Time Algorithm for Cacti
Complexity for Variants
FPT Algorithms
FPT Algorithm for Edge-Coloring Version
FPT Algorithms for Two Variants
References
On Parameterized Independent Feedback Vertex Set
Introduction
An O^*(5^k) Algorithm
A Cubic Kernel
Discussion and Conclusion
References
Cograph Editing: Complexity and Parameterized Algorithms
Introduction
Preliminaries
Notations
Spider Graphs
P_4-Sparse Graphs
NP-Hardness
A Parameterized Algorithm
Editing P_4-Sparse Graphs to Cographs
Editing Graphs to P_4-Sparse Graphs
Conclusions
References
Approximation Complexity of Complex-Weighted Degree-Two Counting Constraint Satisfaction Problems
Bounded-Degree #CSPs
Fundamental Notions and Notations
Signatures, #CSPs, and Holant Problems
FPC and AP-Reducibility
Main Theorems
Symmetric Signatures of Arity 3
Arbitrary Signatures of Arity 3
T_2-Constructibility Technique
Parametrized Symmetrization Technique
Parametrized Symmetrization Scheme
Proof of Proposition 2
References
Strong I/O Lower Bounds for Binomial and FFT Computation Graphs
Introduction
Background
Boundary Flow Technique for Deriving Lower Bounds
Basic Technique
Constrained VIP for Deriving Better Bounds
Memory Traffic Complexity
Binomial Computation Graph
FFT Computation Graph
Conclusion
References
Spin Systems on Graphs with Complex Edge Functions and Specified Degree Regularities
Introduction
Overview of Techniques and Results
Background and Notation
Interpolation Technique
Classification of Complex Signatures
References
Quantum Algorithm for the Boolean Hidden Shift Problem
Introduction
Preliminaries
Our Algorithm
Classical Complexity of Random Instances of BHSP
Discussion and Open Problems
References
A Kolmogorov Complexity Proof of the Lov´asz Local Lemma for Satisfiability
Introduction
The Lovász Local Lemma
Preliminaries
The Kolmogorov Argument
The LOG
Witness Forests
Putting Things Together
An Improvement
Some Remarks on Unsatisfiable k-CNF Formulas
References
Proper n-Cell Polycubes in n -3 Dimensions
Introduction
Overview of the Method
Distinguished Structures
Polycubes with a Tree Structure
Polycubes with One Cycle
Polycubes with Two Cycles
Epilogue
Conclusion
References
Largest Area Convex Hull of Axis-Aligned Squares Based on Imprecise Data
Introduction
Previous Work
O(n^7) Algorithm for Problem 1
O(n^5) Algorithm for Problem 2
O(n^5) Algorithm for Problem 1
O(n^3) Algorithm for Problem 2
Conclusions
References
Improved Algorithms for the Point-Set Embeddability Problem for Plane 3-Trees
Introduction
Preliminaries
Algorithms
Analysis
For Points Not in General Positions
Conclusion
References
Optimal Strategies for the One-Round Discrete Voronoi Game on a Line
Introduction
Optimal Strategy of P2
Optimal Strategy of P1
An Important Lemma
A Characterization of the Optimal Placement by P1
Improving the Algorithm for the Optimal Strategy of P1
m=2
Extending to the General Case
Conclusions
References
Computing the Girth of a Planar Graph in Linear Time
Introduction
Preliminaries
Expanded Version, Density, and Contracted Graph
Outerplane Radius and Degree Reduction
Proving the Theorem by the Main Lemma
Dissection Tree, Nonleaf Problem, and Leaf Problem
Task 1: Computing a Dissection Tree
Task 2: Solving the Nonleaf Problems
A Reduction to the Border Problems for the Special Leaf Vertices
Solving the Border Problems for the Special Leaf Vertices
Task 3: Solving the Leaf Problem
Concluding Remarks
References
Diagonalization Strikes Back: Some Recent Lower Bounds in Complexity Theory
References
Unions of Disjoint NP-Complete Sets
Introduction
Preliminaries
Main Theorems
Length-Increasing Reductions
Discussion
References
ReachFewL = ReachUL
Introduction
Definitions and Necessary Results
ReachUL as an Oracle
Converting Graphs with a Few Paths to Distance Isolated Graphs
Converting Distance Isolated Graphs to Unambiguous Graphs
ReachFewL= ReachUL
Discussion
References
(1 + e)-Competitive Algorithm for Online OVSF Code Assignment with Resource Augmentation
Introduction
Preliminaries
2-Competitive Algorithm with 2lg*h Trees
Preparation of Subtrees
Labeling Subtrees
Algorithm ALG_1
(1+1/a)-Competitive Algorithm with (1 + [a]) lg* h Trees
Preparation of Subtrees
Labeling Subtrees
Algorithm ALG_a
References
Scheduling Jobs on Heterogeneous Platforms
Introduction
An AFPTAS for SPP
Relaxed Schedule
Rounding the Fractional Solution
Strip Packing Subroutine
Analysis
Analyzing the Output
Running Time of the Algorithm
Malleable Jobs
Release Times
References
Self-assembling Rulers for Approximating Generalized Sierpinski Carpets
Introduction
Preliminaries
Embedded Fractals
Approximating Generalized Sierpinski Carpets
Rulers and Readers
Putting It all Together
Conclusion
References
Approximately Uniform Online Checkpointing
Introduction
Model
Checkpointing Algorithms
Powers-of-Two Algorithm
Golden Ratio Approach
Golden Ratio Algorithms
Optimal Algorithm for k=2
Lower Bound for Competitive Ratio
Conclusions and Future Work
References
Bandwidth of Convex Bipartite Graphs and Related Graphs
Introduction
Bandwidth of Convex Bipartite Graphs
NP-Completeness Result
Approximation Algorithms for Convex Bipartite Graphs
Bandwidth of 2-Directional Orthogonal Ray Graphs
Bandwidth of Biconvex Trees
References
Algorithms for Partition of Some Class of Graphs under Compaction
Introduction
Some Requirements for Compaction
Compaction to Reflexive and Irreflexive Paths
Compaction to Reflexive and Irreflexive Graphs through a Walk
An Algorithm for the Partition Problem COMP-H for Some Class of Input Graphs when H Is Reflexive
An Algorithm for the Partition Problem COMP-H for Some Class of Input Graphs when H Is Irreflexive
Structure of Graphs for Compaction to Cycles
References
A Generic Approach to Decomposition Algorithms, with an Application to Digraph Decomposition
Introduction
Efficient Tree Representations of Set Families
A Module-Split Digraph Decomposition
Splitmodules of Digraphs
A Tree Representation for Splitmodules
Conclusion
References
Matching and P_2-Packing: Weighted Versions
Introduction
Constrained P_2-Packings on Bipartite Graphs
Improved Algorithms for the P_2-Packing Problem
Conclusion
References
On Totally Unimodularity of Edge-Edge Adjacency Matrices
Introduction
Preliminaries
A Necessary and Sufficient Condition on Totally Unimodularity of EE Matrices
Necessary Condition
Sufficient Condition
Conclusion
References
The Topology Aware File Distribution Problem
Introduction
Related Work
The Router Topology Aware (RTA) Network Model
An O(logn)-Approximation
Max-Min Edge Workstation Spanning Tree, MMWST
Tree Splitting, TREESPLIT
NP-Completeness
Conclusion
References
Exploiting the Robustness on Power-Law Networks
Introduction
Models, Measurement and Threat Taxonomy
Power-Law Random Graph Model (PLRG)
Vulnerability Measurements
Threat Taxonomy
Preliminaries
Uniform Random Failures
Preferential Attacks
Interactive Attacks ( pi = 1- 1/i^ß')
Expected Attacks ( pi = c i/e^a?(ß-1) )
Degree-Centrality Attacks
References
Competitive Algorithms for Online Pricing
Introduction
h Is Known in Advance
Lower Bound
Online Algorithm
h Is Not Known in Advance
References
Making Abstraction-Refinement EÆcient in Model Checking
Introduction
Related Work
Abstraction Function
Refinement
Why Refining?
Spurious Counterexamples
Refining Algorithm
Abstract Model Checking Framework
Conclusion
References
An Integer Programming Approach for the Rural Postman Problem with Time Dependent Travel Times
Introduction
Problem Formulation
Results on RPPTDT Polyhedron
Computational Results
Application in Scheduling with Time Dependent Processing Times
Conclusions
References
Property Testing for Cyclic Groups and Beyond
Introduction
Definitions
A Lower Bound for Testing Cyclic Groups
A Lower Bound for Testing the Number of Generators in a Group
Testing If the Input Is Cyclic When |G| Is Known
References
Canonizing Hypergraphs under Abelian Group Action
Introduction
Complexity Classes
Preliminary Observations
Canonizing Hypergraphs with Color Classes of Size 2
Canonizing Hypergraphs under Abelian Groups
References
Linear Time Algorithms for the Basis of Abelian Groups
Introduction
Preliminaries
Our Results
Auxiliary Results
The Extended Discrete Logarithm Problem
The BASIS Algorithm
The ORDER-FINDING Algorithm
Computing the Order of an Element in O((logN)2loglogN)-Time
Presentation of Our Algorithms
First Proof of O(N)-Time Algorithm
Second Proof of O(N)-Time Algorithm
Proof of Corollary 1
Conclusion
References
Characterizations of Locally Testable Linear andAffine-Invariant Families
Introduction
Theorems and Methods
Constraints on Affine/Linear-Invariant Families
Characterizations for Linear-Invariant Families
Generalization to Extension Fields
References
A New Conditionally Anonymous Ring Signature
Introduction
Preliminaries
Model of Conditionally Anonymous Ring Signature
Syntax
Oracles
Security Model
Construction
Performance
Security
Conclusion
References
On the Right-Seed Array of a String
Definitions and Problems
Properties
The Algorithms
A Brief Description of the Partitioning Algorithm
Computing the Minimal and the Maximal Right-Seed Array
Further Works
References
Compressed Directed Acyclic Word Graph with Application in Local Alignment
Introduction
Basic Concepts and Definitions
Suffix Array and Suffix Tree
Advanced Data-Structures for Suffix Array and Suffix Tree
Directed Acyclic Word Graph
Simulating DAWG
Get-Source Operation
End-Set Operations
Child Operation
Parent Operations
Application of DAWG in Local Alignment
Definitions of Global, Local, and Meaningful Alignments
Local Alignment Using DAWG
References
Unavoidable Regularities in Long Words with Bounded Number of Symbol Occurrences
Introduction
Basics on Alphabets and Words
The Main Theorem
Further Considerations on Permutations
Connections to Multicollision Attacks on Generalized Iterated Hash Functions
Generalization in Practice
Conclusion
References
Summing Symbols in Mutual Recurrences
Problem Statement
Related Work
Systems of Mutual Recurrences
Homogeneous Case
Inhomogeneous Case
The Summation Procedure
Analysis
Conclusion
References
Flipping Triangles and Rectangles
Introduction
Flipping Triangles
Chromatic Number
Clique-Partition Number
Independence Number
Imperfection Ratio and Fractional Chromatic Number
Flipping Rectangles
Rolling Blocks
Open Question
References
Unconstained and Constrained Fault-Tolerant Resource Allocation
Introduction
Unconstrained FTRA
The Algorithms
Analysis: Dual Fitting and Inverse Dual Fitting
Capacitated UFTRA
Constrained FTRA
References
Finding Paths with Minimum Shared Edges
Introduction
NP-Hardness Proof
Approximation Algorithm
Inapproximability Result
Heuristic Improvements
Successive Cost Update
Shortest Path Bound
Experimental Results
Conclusions
References
Combinatorial Group Testing for Corruption Localizing Hashing
Introduction
Model and Preliminaries
Using Localizing Codes for Corruption Localization
A First Localizing Code
A Localizing Code Achieving Constant Localization Factor
References
Task Ordering and Memory Management Problem for Degree of Parallelism Estimation
Introduction
Related Work
Problem Formulation and Complexity
Memory Management for a Fixed Sequence of Tasks
Task Ordering and Memory Management
Branching Rule
Lower Bounds
Dominance Relation
Selection Rules
Computational Results
Conclusion
References
Computing Majority with Triple Queries
Introduction
Model of Computation
Notation
Related Work
Outline and Results of the Paper
Existence of Solutions
Y/N Model
The Upper Bound
The Lower Bound
Pairing Model
A General Lower Bound
Determining q_3^p (n)
Conclusion
References
A New Variation of Hat Guessing Games
Introduction
Preliminaries
(d1,d2)-Regular Partition of Q_n
The Maximum Winning Probability P_n,k
Conclusion
References
Oblivious Transfer and n-Variate Linear Function Evaluation
Introduction
Preliminaries
Statistically Secure Reduction from (n 1)-OT to C-OLFE_n
C-OLFEn and Reversing (n 1)-OT
Conclusion
References
Optimal Online Algorithms on Two Hierarchical Machines with Resource Augmentation
Introduction
Optimal Algorithm for 0&q, s1
Optimal Algorithm for q, s&1
Conclusions
References
Author Index

Systemvoraussetzungen

Als PDF speichern Als Link merken