LEADER 07204nam 22008175 450 001 996465766203316 005 20230221011843.0 010 $a1-280-95658-5 010 $a9786610956586 010 $a3-540-72504-0 024 7 $a10.1007/978-3-540-72504-6 035 $a(CKB)1000000000491034 035 $a(EBL)3061646 035 $a(SSID)ssj0000311358 035 $a(PQKBManifestationID)11233011 035 $a(PQKBTitleCode)TC0000311358 035 $a(PQKBWorkID)10315161 035 $a(PQKB)11146236 035 $a(DE-He213)978-3-540-72504-6 035 $a(MiAaPQ)EBC3061646 035 $a(MiAaPQ)EBC6700657 035 $a(Au-PeEL)EBL6700657 035 $a(PPN)123727545 035 $a(EXLCZ)991000000000491034 100 $a20100301d2007 u| 0 101 0 $aeng 135 $aur|n|---||||| 181 $ctxt 182 $cc 183 $acr 200 10$aTheory and Applications of Models of Computation$b[electronic resource] $e4th International Conference, TAMC 2007, Shanghai, China, May 22-25, 2007, Proceedings /$fedited by Jin-Yi Cai, Barry S. Cooper, Hong Zhu 205 $a1st ed. 2007. 210 1$aBerlin, Heidelberg :$cSpringer Berlin Heidelberg :$cImprint: Springer,$d2007. 215 $a1 online resource (783 p.) 225 1 $aTheoretical Computer Science and General Issues,$x2512-2029 ;$v4484 300 $aDescription based upon print version of record. 311 $a3-540-72503-2 320 $aIncludes bibliographical references and index. 327 $aPlenary 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. 410 0$aTheoretical Computer Science and General Issues,$x2512-2029 ;$v4484 606 $aComputer science 606 $aAlgorithms 606 $aArtificial intelligence 606 $aComputer science?Mathematics 606 $aBioinformatics 606 $aTheory of Computation 606 $aAlgorithms 606 $aArtificial Intelligence 606 $aMathematics of Computing 606 $aBioinformatics 615 0$aComputer science. 615 0$aAlgorithms. 615 0$aArtificial intelligence. 615 0$aComputer science?Mathematics. 615 0$aBioinformatics. 615 14$aTheory of Computation. 615 24$aAlgorithms. 615 24$aArtificial Intelligence. 615 24$aMathematics of Computing. 615 24$aBioinformatics. 676 $a511.3 702 $aCooper$b S. B$g(S. Barry), 702 $aCai$b Jin-yi$f1961- 702 $aZhu$b Hong$f1961- 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a996465766203316 996 $aTheory and Applications of Models of Computation$9772738 997 $aUNISA