Communications of the ACM
Targeted Results
Ibiblio.org
Massachusetts Institute of Technology (MIT) and Tel Aviv University researchers recently met at the Innovations in Computer Science conference at Tsinghua University to present a mathematical framework for finding localized solutions to complex calculations. The researchers say the framework could be used to solve classic computer science problems involving mathematical abstractions known as graphs.
Graphs can represent any type of data, but it is often useful to determine the graph's maximal independent set, which occurs when enough vertices have been deleted from the graph so that there are no edges left, meaning that none are connected to any other. Graphs also can have more than one maximal independent set.
The researchers developed an algorithm to efficiently determine which vertices are and are not included in at least one of the graph's maximal independent sets. Although the research is theoretical, the problem of calculating independent sets cuts across a variety disciplines, including artificial intelligence, bioinformatics, and scheduling and networking.
"There have been lots of related concepts that have been sort of floating around," but the MIT and Tel Aviv researchers "have formalized it in an interesting way and, I think, the correct way," says Sandia National Labs' Seshadhri Comandur.
From MIT News
View Full Article
No entries found