Computer Forum

My Computer Forum: for a better understanding of computers and computer science

Web Programming Languages Tutorials
Learn HTML Learn PHP basics Learn Advanced PHP Learn SQL with MySQL Learn CSS
What is HTML ? Introduction to PHP scripts PHP include() and PHP require() SQL queries in your PHP scripts Tables creation and box structure
Structure of HTML files PHP output functions (echo, print) Defining functions in PHP Connecting to a MySQL database server Use of class and div in HTML/CSS
Text/fonts, links, images PHP variables Using HTML forms in PHP Creating or deleting a MySQL database Example
Blocks, paragraphs, lists, tables Conditional statements and loops PHP Sessions Creating MySQL database tables
Meta tags and Search Engine Optimization PHP operators PHP cookies handling Creating MySQL database entries
Insertion of scripts (javascript, php, mysql, css) PHP arrays and arrays of arrays PHP files handling MySQL database search (SQL function SELECT)
PHP strings and string functions SQL queries in PHP

decide if a graph contains a triangle

Analysis of algorithms, Algorithms, Data structures. Get help with graph algorithms, search algorithms, string algorithms, sorting algorithms, merge algorithms, compression algorithms, optimization and quantum algorithms on My Computer Forum

Moderators: shynthriir, johnny, SidT

Post a reply

decide if a graph contains a triangle

Postby becko » Thu Jun 17, 2010 12:44 am

Devise an algorithm that will decide if a given graph of n vertices and m edges does or does not contain a triangle (K3), in time O(max{n^2, mn}).

I found this problem in ch.1 of Algorithms and Complexity by H S Wilf. Any ideas are appreciated. Or if you know of some place where an algorithm to do this is explained, tell me. Thanks.
becko
 
Posts: 1
Joined: Thu Jun 17, 2010 12:29 am
Top
Post a reply

Return to Algorithms and Data Structures

Who is online

Registered users: Ask Jeeves [Bot]


Copyright © My Computer Forum 2007
cron