Theory and Applications of Models of Computation: 4th International Conference, TAMC 2007, Shanghai, China, May 22-25, 2007. Proceedings

Front Matter....Pages -
Detecting Sharp Drops in PageRank and a Simplified Local Partitioning Algorithm....Pages 1-12
Generalizations of the Compactness Theorem and Gödel’s Completeness Theorem for Nonstandard Finite Structures....Pages 13-33
Approximation Algorithms for 3D Orthogonal Knapsack....Pages 34-45
A Comparative Study of Efficient Algorithms for Partitioning a Sequence into Monotone Subsequences....Pages 46-57
The Hardness of Selective Network Design for Bottleneck Routing Games....Pages 58-66
A Polynomial Time Algorithm for Finding Linear Interval Graph Patterns....Pages 67-78
Elementary Differences Among Jump Hierarchies....Pages 79-88
Working with the LR Degrees....Pages 89-99
Computability on Subsets of Locally Compact Spaces....Pages 100-114
A New Approach to Graph Recognition and Applications to Distance-Hereditary Graphs....Pages 115-127
Finding a Duplicate and a Missing Item in a Stream....Pages 128-135
Directed Searching Digraphs: Monotonicity and Complexity....Pages 136-147
Protecting Against Key Escrow and Key Exposure in Identity-Based Cryptosystem....Pages 148-158
Encapsulated Scalar Multiplications and Line Functions in the Computation of Tate Pairing....Pages 159-170
A Provably Secure Blind Signature Scheme....Pages 171-180
Construct Public Key Encryption Scheme Using Ergodic Matrices over GF(2)....Pages 181-188
New Left-to-Right Radix- r Signed-Digit Recoding Algorithm for Pairing-Based Cryptosystems....Pages 189-198
The Strongest Nonsplitting Theorem....Pages 199-211
There is an Sw-Cuppable Strongly c.e. Real....Pages 212-221
On Computation Complexity of the Concurrently Enabled Transition Set Problem....Pages 222-233
Synchronization of Some DFA....Pages 234-243
On the Treewidth and Pathwidth of Biconvex Bipartite Graphs....Pages 244-255
On Exact Complexity of Subgraph Homeomorphism....Pages 256-261
Searching a Polygonal Region by Two Guards....Pages 262-273
On the Internal Steiner Tree Problem....Pages 274-283
Approximately Optimal Trees for Group Key Management with Batch Updates....Pages 284-295
On Deciding Deep Holes of Reed-Solomon Codes....Pages 296-305
Quantum Multiparty Communication Complexity and Circuit Lower Bounds....Pages 306-317
Efficient Computation of Algebraic Immunity of Symmetric Boolean Functions....Pages 318-329
Improving the Average Delay of Sorting....Pages 330-341
Approximating Capacitated Tree-Routings in Networks....Pages 342-353
Feedback Arc Set Problem in Bipartite Tournaments....Pages 354-361
Studying on Economic-Inspired Mechanisms for Routing and Forwarding in Wireless Ad Hoc Network....Pages 362-373
Enhancing Simulation for Checking Language Containment....Pages 374-385
QBF-Based Symbolic Model Checking for Knowledge and Time....Pages 386-397
A Characterization of the Language Classes Learnable with Correction Queries....Pages 398-407
Learnable Algorithm on the Continuum....Pages 408-415
Online Deadline Scheduling with Bounded Energy Efficiency....Pages 416-427
Efficient Algorithms for Airline Problem....Pages 428-439
Efficient Exact Arithmetic over Constructive Reals....Pages 440-449
Bounding Run-Times of Local Adiabatic Algorithms....Pages 450-461
A Note on Universal Composable Zero Knowledge in Common Reference String Model....Pages 462-473
A Note on the Feasibility of Generalized Universal Composability....Pages 474-485
 t -Private and Secure Auctions....Pages 486-498
Secure Multiparty Computations Using a Dial Lock....Pages 499-510
A Time Hierarchy Theorem for Nondeterministic Cellular Automata....Pages 511-520
Decidability of Propositional Projection Temporal Logic with Infinite Models....Pages 521-532
Separation of Data Via Concurrently Determined Discriminant Functions....Pages 533-541
The Undecidability of the Generalized Collatz Problem....Pages 542-553
Combinatorial and Spectral Aspects of Nearest Neighbor Graphs in Doubling Dimensional and Nearly-Euclidean Spaces....Pages 554-565
Maximum Edge-Disjoint Paths Problem in Planar Graphs....Pages 566-572
An Efficient Algorithm for Generating Colored Outerplanar Graphs....Pages 573-583
Orthogonal Drawings for Plane Graphs with Specified Face Areas....Pages 584-594
Absolutely Non-effective Predicates and Functions in Computable Analysis....Pages 595-604
Linear-Size Log-Depth Negation-Limited Inverter for k -Tonic Binary Sequences....Pages 605-615
The Existence of Unsatisfiable Formulas in k -LCNF for k  ≥ 3....Pages 616-623
Improved Exponential Time Lower Bound of Knapsack Problem Under BT Model....Pages 624-631
Phase Transition of Multivariate Polynomial Systems....Pages 632-645
Approximation Algorithms for Maximum Edge Coloring Problem....Pages 646-658
Two Improved Range-Efficient Algorithms for F 0 Estimation....Pages 659-669
Approximation to the Minimum Rooted Star Cover Problem....Pages 670-679
Approximability and Parameterized Complexity of Consecutive Ones Submatrix Problems....Pages 680-691
Parameterized Algorithms for Weighted Matching and Packing Problems....Pages 692-702
Kernelizations for Parameterized Counting Problems....Pages 703-714
Revisiting the Impossibility for Boosting Service Resilience....Pages 715-727
An Approximation Algorithm to the k -Steiner Forest Problem....Pages 728-737
A Distributed Algorithm of Fault Recovery for Stateful Failover....Pages 738-749
Path Embedding on Folded Hypercubes....Pages 750-759
An Approximation Algorithm Based on Chain Implication for Constrained Minimum Vertex Covers in Bipartite Graphs....Pages 760-769
Back Matter....Pages -