This book constitutes the refereed proceedings of the Third International Frontiers of Algorithmics Workshop, FAW 2009, held in Hefei, Anhui, China, in June 2009.
The 33 revised full papers presented together with the abstracts of 3 invited talks were carefully reviewed and selected from 87 submissions. The papers are organized in topical sections on graph algorithms; game theory with applications; graph theory, computational geometry; machine learning; parameterized algorithms, heuristics and analysis; approximation algorithms; as well as pattern recognition algorithms, large scale data mining.
Author(s): Guoliang Chen (auth.), Xiaotie Deng, John E. Hopcroft, Jinyun Xue (eds.)
Series: Lecture Notes in Computer Science 5598 : Theoretical Computer Science and General Issues
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2009
Language: English
Pages: 372
City: Philadelphia
Tags: Algorithm Analysis and Problem Complexity; Discrete Mathematics in Computer Science; Software Engineering/Programming and Operating Systems; Computer Communication Networks; Data Mining and Knowledge Discovery; Algorithms
Front Matter....Pages -
CFI Construction and Balanced Graphs....Pages 97-107
Minimizing the Weighted Directed Hausdorff Distance between Colored Point Sets under Translations and Rigid Motions....Pages 108-119
Space–Query-Time Tradeoff for Computing the Visibility Polygon....Pages 120-131
Square and Rectangle Covering with Outliers....Pages 132-140
Processing an Offline Insertion-Query Sequence with Applications....Pages 141-152
Bounds on the Geometric Mean of Arc Lengths for Bounded-Degree Planar Graphs....Pages 153-162
On Minimizing One Dimension of Some Two-Dimensional Geometric Representations of Plane Graphs....Pages 163-172
On Modulo Linked Graphs....Pages 173-180
Pathwidth is NP-Hard for Weighted Trees....Pages 181-195
Study on Parallel Computing....Pages 1-1
Communication Complexity and Its Applications....Pages 2-2
Algorithmic Problems in Computer and Network Power Management....Pages 3-3
Shortest Path and Maximum Flow Problems in Networks with Additive Losses and Gains....Pages 4-15
Edge Search Number of Cographs in Linear Time....Pages 16-26
Formal Derivation of a High-Trustworthy Generic Algorithmic Program for Solving a Class of Path Problems....Pages 27-39
Improved Algorithms for Detecting Negative Cost Cycles in Undirected Graphs....Pages 40-50
Covering-Based Routing Algorithms for Cyclic Content-Based P/S System....Pages 51-62
On the α -Sensitivity of Nash Equilibria in PageRank-Based Network Reputation Games....Pages 63-73
Cop-Robber Guarding Game with Cycle Robber Region....Pages 74-84
Covered Interest Arbitrage in Exchange Rate Forecasting Markets....Pages 85-96
A Max-Margin Learning Algorithm with Additional Features....Pages 196-206
DDoS Attack Detection Algorithm Using IP Address Features....Pages 207-215
Learning with Sequential Minimal Transductive Support Vector Machine....Pages 216-227
Junction Tree Factored Particle Inference Algorithm for Multi-Agent Dynamic Influence Diagrams....Pages 228-236
An Efficient Fixed-Parameter Enumeration Algorithm for Weighted Edge Dominating Set....Pages 237-250
Heuristics for Mobile Object Tracking Problem in Wireless Sensor Networks....Pages 251-260
Efficient Algorithms for the Closest String and Distinguishing String Selection Problems....Pages 261-270
The BDD-Based Dynamic A* Algorithm for Real-Time Replanning....Pages 271-282
Approximating Scheduling Machines with Capacity Constraints....Pages 283-292
Approximating the Spanning k -Tree Forest Problem....Pages 293-301
Toward an Automatic Approach to Greedy Algorithms....Pages 302-313
A Novel Approximate Algorithm for Admission Control....Pages 314-325
On the Structure of Consistent Partitions of Substring Set of a Word....Pages 326-335
A Bit-Parallel Exact String Matching Algorithm for Small Alphabet....Pages 336-345
An Improved Database Classification Algorithm for Multi-database Mining....Pages 346-357
Six-Card Secure AND and Four-Card Secure XOR....Pages 358-369
Back Matter....Pages -
