Theory and Applications of Models of Computation : 4th International Conference, TAMC 2007, Shanghai, China, May 22-25, 2007, Proceedings / edited by Jin-Yi Cai, Barry S. Cooper, Hong Zhu.

Format:

Book

Contributor:

Cai, Jin-yi, 1961- editor.

Cooper, Barry S., editor.

Zhu, Hong, 1961- editor.

SpringerLink (Online service)

Series:

Computer Science (Springer-11645)

LNCS sublibrary. Theoretical computer science and general issues ; SL 1, 4484.

Theoretical Computer Science and General Issues ; 4484

Language:

English

Subjects (All):

Computers.

Algorithms.

Artificial intelligence.

Computer science--Mathematics.

Computer science.

Bioinformatics.

Theory of Computation.

Algorithm Analysis and Problem Complexity.

Computation by Abstract Devices.

Artificial Intelligence.

Mathematics of Computing.

Local Subjects:

Theory of Computation.

Algorithm Analysis and Problem Complexity.

Computation by Abstract Devices.

Artificial Intelligence.

Mathematics of Computing.

Bioinformatics.

Physical Description:

1 online resource (XIII, 772 pages).

Edition:

First edition 2007.

Contained In:

Springer eBooks

Place of Publication:

Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer, 2007.

System Details:

text file PDF

Contents:

Plenary Lectures

Detecting Sharp Drops in PageRank and a Simplified Local Partitioning Algorithm

Generalizations of the Compactness Theorem and Gödel's Completeness Theorem for Nonstandard Finite Structures

Contributed Papers

Approximation Algorithms for 3D Orthogonal Knapsack

A Comparative Study of Efficient Algorithms for Partitioning a Sequence into Monotone Subsequences

The Hardness of Selective Network Design for Bottleneck Routing Games

A Polynomial Time Algorithm for Finding Linear Interval Graph Patterns

Elementary Differences Among Jump Hierarchies

Working with the LR Degrees

Computability on Subsets of Locally Compact Spaces

A New Approach to Graph Recognition and Applications to Distance-Hereditary Graphs

Finding a Duplicate and a Missing Item in a Stream

Directed Searching Digraphs: Monotonicity and Complexity

Protecting Against Key Escrow and Key Exposure in Identity-Based Cryptosystem

Encapsulated Scalar Multiplications and Line Functions in the Computation of Tate Pairing

A Provably Secure Blind Signature Scheme

Construct Public Key Encryption Scheme Using Ergodic Matrices over GF(2)

New Left-to-Right Radix-r Signed-Digit Recoding Algorithm for Pairing-Based Cryptosystems

The Strongest Nonsplitting Theorem

There is an Sw-Cuppable Strongly c.e. Real

On Computation Complexity of the Concurrently Enabled Transition Set Problem

Synchronization of Some DFA

On the Treewidth and Pathwidth of Biconvex Bipartite Graphs

On Exact Complexity of Subgraph Homeomorphism

Searching a Polygonal Region by Two Guards

On the Internal Steiner Tree Problem

Approximately Optimal Trees for Group Key Management with Batch Updates

On Deciding Deep Holes of Reed-Solomon Codes

Quantum Multiparty Communication Complexity and Circuit Lower Bounds

Efficient Computation of Algebraic Immunity of Symmetric Boolean Functions

Improving the Average Delay of Sorting

Approximating Capacitated Tree-Routings in Networks

Feedback Arc Set Problem in Bipartite Tournaments

Studying on Economic-Inspired Mechanisms for Routing and Forwarding in Wireless Ad Hoc Network

Enhancing Simulation for Checking Language Containment

QBF-Based Symbolic Model Checking for Knowledge and Time

A Characterization of the Language Classes Learnable with Correction Queries

Learnable Algorithm on the Continuum

Online Deadline Scheduling with Bounded Energy Efficiency

Efficient Algorithms for Airline Problem

Efficient Exact Arithmetic over Constructive Reals

Bounding Run-Times of Local Adiabatic Algorithms

A Note on Universal Composable Zero Knowledge in Common Reference String Model

A Note on the Feasibility of Generalized Universal Composability

t-Private and Secure Auctions

Secure Multiparty Computations Using a Dial Lock

A Time Hierarchy Theorem for Nondeterministic Cellular Automata

Decidability of Propositional Projection Temporal Logic with Infinite Models

Separation of Data Via Concurrently Determined Discriminant Functions

The Undecidability of the Generalized Collatz Problem

Combinatorial and Spectral Aspects of Nearest Neighbor Graphs in Doubling Dimensional and Nearly-Euclidean Spaces

Maximum Edge-Disjoint Paths Problem in Planar Graphs

An Efficient Algorithm for Generating Colored Outerplanar Graphs

Orthogonal Drawings for Plane Graphs with Specified Face Areas

Absolutely Non-effective Predicates and Functions in Computable Analysis

Linear-Size Log-Depth Negation-Limited Inverter for k-Tonic Binary Sequences

The Existence of Unsatisfiable Formulas in k-LCNF for k???3

Improved Exponential Time Lower Bound of Knapsack Problem Under BT Model

Phase Transition of Multivariate Polynomial Systems

Approximation Algorithms for Maximum Edge Coloring Problem

Two Improved Range-Efficient Algorithms for F 0 Estimation

Approximation to the Minimum Rooted Star Cover Problem

Approximability and Parameterized Complexity of Consecutive Ones Submatrix Problems

Parameterized Algorithms for Weighted Matching and Packing Problems

Kernelizations for Parameterized Counting Problems

Revisiting the Impossibility for Boosting Service Resilience

An Approximation Algorithm to the k-Steiner Forest Problem

A Distributed Algorithm of Fault Recovery for Stateful Failover

Path Embedding on Folded Hypercubes

An Approximation Algorithm Based on Chain Implication for Constrained Minimum Vertex Covers in Bipartite Graphs.

Other Format:

Printed edition:

ISBN:

978-3-540-72504-6

9783540725046

Access Restriction:

Restricted for use by site license.