The Time Complexity of Hsu and Huang's Self-Stabilizing Maximal Matching Algorithm

スポンサーリンク

概要

論文の詳細を見る
The exact time complexity of Hsu and Huans self-stabilizing maximal matching algorithm is provided. It is $\\frac{1}{2}n^2 + n - 2$ if the number of nodes n is even and $\\frac{1}{2}n^2 + n - \\frac{5}{2}$ if n is odd.
（社）電子情報通信学会の論文
2010-10-01

著者

関連論文

On the Time Complexity of Dijkstra's Three-State Mutual Exclusion Algorithm
An Effective Testing Method for Hardware Related Fault in Embedded Software(Software Engineering for Embedded Systems)
Feature Interaction Detection by Bounded Model Checking(Dependable Communication)(Dependable Computing)
Software Project Simulator for Effective Process Improvement (特集〔情報処理学会〕創立40周年記念論文)
Verifying Fault Tolerance of Concurrent Systems by Model Checking(Special Section on Concurrent System Technology and Its Application to Multiple Agent Systems)
A Hierarchical Approach to Dependability Evaluation of Distributed Systems with Replicated Resources
New Constructions for Nondominated k-Coteries
Constructing a Bayesian Belief Network to Predict Final Quality in Embedded System Development(Software Engineering for Embedded Systems)
Test Item Prioritizing Metrics for Selective Software Testing(Software Engineering)
Enhancing Software Project Simulator toward Risk Prediction with Cost Estimation Capability(Special Section on Concurrent Systems Technology)
Experimental Evaluation of Two-Phase Project Control for Software Development Process(Special Section on Concurrent Systems Technology)
A New Verification Method Using Virtual System States for Responsive Communication Protocols and Its Application to a Broadcasting Protocol(Special Section on Concurrent Systems Technology)
Timed Reachability Analysis Method for Communication Protocols Modeled by Extended Finite State Machines (Special Issue on Multimedia Communication and Distributed Processing)
Experimental Evaluation of Processor Scheduling Algorithm for Parallel Logic Simulation Using Benchmark Circuits
Model Checking Active Database Rules under Various Rule Processing Strategies
The Time Complexity of Hsu and Huang's Self-Stabilizing Maximal Matching Algorithm
Analysis of Rollbacks in Parallel Logic Simulation Based on Virtual Time*
Using Satisfiability Solving for Pairwise Testing in the Presence of Constraints
Model Checking Active Database Rules under Various Rule Processing Strategies
Using Satisfiability Solving for Pairwise Testing in the Presence of Constraints

もっと見る

スポンサーリンク