Sensor networks and distributed CSP: communication, computation and complexity

DOI10.1016/j.artint.2004.09.002zbMath1132.68688MaRDI QIDQ2457701

Bhaskar Krishnamachari, Carmel Domshlak, Magda Valls, Ramón Béjar, Carla P. Gomes, Bart Selman, Cèsar Fernández

Publication date: 23 October 2007

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/10459.1/57458

zbMATH Keywords

phase transitions; NP-completeness; communication network delays; distributed CSP benchmark; randomized combinatorial search

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

68M14: Distributed systems

68W15: Distributed algorithms

Related Items

SensorDCSP, Nogood-based asynchronous forward checking algorithms, Message delay and DisCSP search algorithms, Reordering all agents in asynchronous backtracking for distributed constraint satisfaction problems, An efficient distributed optimization and coordination protocol: application to the emergency vehicle management

Uses Software

• SATLIB
• CNCL

Cites Work

• Complexity results for standard benchmark domains in planning
• A distributed arc-consistency algorithm
• On the Complexity of General Graph Factor Problems
• Multistage negotiation for distributed constraint satisfaction
• Determining computational complexity from characteristic ‘phase transitions’
• Principles and Practice of Constraint Programming – CP 2003
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item