@

Dark Mode

Profile
Edit my Profile
Messages
My favorites

Register

Activity
Q&A
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous Years
Blogs
New Blog
Exams

Dark Mode

Gate 2005

Ketan Dhakate asked in Algorithms Jun 6, 2017 retagged Jun 25, 2022 by makhdoom ghaya

646 views

0 votes

0 votes

The time complexity of computing the transitive closure of binary relation on set of n element is known to be:-

algorithms
gatecse-2005
time-complexity

Ketan Dhakate asked in Algorithms Jun 6, 2017 retagged Jun 25, 2022 by makhdoom ghaya

by Ketan Dhakate

646 views

0 Comments

Please log in or register to add a comment.

Please log in or register to answer this question.

1 Answer

0 votes

0 votes

Warshall’s algorithm can be used to construct the Transitive closure of directed graphs ()

so O(n³)

https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

http://en.wikipedia.org/wiki/Transitive_closure

pawan kumarln answered Jun 7, 2017

by pawan kumarln

0 Comments

Please log in or register to add a comment.

← Previous Next →

← Previous in category Next in category →

Related questions

23 votes

23 votes

3 answers

1

go_editor asked in Algorithms Nov 15, 2016

4,936 views

GATE CSE 2005 | Question: 84b
We are given $9$ tasks $T_1, T_2, \dots, T_9$. The execution of each task requires one unit of time. We can execute one task at a time. Each task $T_i$ has a profit $P_i$ and a deadline $d_i$. Profit $P_i$ is earned if the task is completed before the end ... $} & \text{$3$} \\\hline \end{array}$ What is the maximum profit earned? $147$ $165$ $167$ $175$

go_editor asked in Algorithms Nov 15, 2016

4.9k views

gatecse-2005
algorithms
greedy-algorithm
process-scheduling
normal

43 votes

43 votes

5 answers

2

go_editor asked in Algorithms Nov 14, 2016

6,483 views

GATE CSE 2005 | Question: 82b
Let $s$ and $t$ be two vertices in a undirected graph $G=(V,E)$ having distinct positive edge weights. Let $[X,Y]$ be a partition of $V$ such that $s \in X$ and $t \in Y$. Consider the edge $e$ having the minimum weight amongst all those edges ... spanning tree a weighted shortest path from $s$ to $t$ an Euler walk from $s$ to $t$ a Hamiltonian path from $s$ to $t$

go_editor asked in Algorithms Nov 14, 2016

6.5k views

gatecse-2005
algorithms
graph-algorithms
normal

30 votes

30 votes

4 answers

3

Kathleen asked in Algorithms Sep 22, 2014

13,649 views

GATE CSE 2005 | Question: 84a
We are given $9$ tasks $T_1, T_2, \dots, T_9$. The execution of each task requires one unit of time. We can execute one task at a time. Each task $T_i$ has a profit $P_i$ and a deadline $d_i$. Profit $P_i$ is earned if the task is completed before ... profit? All tasks are completed $T_1$ and $T_6$ are left out $T_1$ and $T_8$ are left out $T_4$ and $T_6$ are left out

Kathleen asked in Algorithms Sep 22, 2014

13.6k views

gatecse-2005
algorithms
greedy-algorithm
process-scheduling
normal

40 votes

40 votes

10 answers

4

Kathleen asked in Algorithms Sep 22, 2014

12,750 views

GATE CSE 2005 | Question: 82a
Let $s$ and $t$ be two vertices in a undirected graph $G=(V,E)$ having distinct positive edge weights. Let $[X,Y]$ be a partition of $V$ such that $s \in X$ and $t \in Y$. Consider the edge $e$ having the minimum weight amongst all those edges that ... of $G$ the weighted shortest path from $s$ to $t$ each path from $s$ to $t$ the weighted longest path from $s$ to $t$

Kathleen asked in Algorithms Sep 22, 2014

12.8k views

gatecse-2005
algorithms
graph-algorithms
normal

Subscribe to GATE CSE 2024 Test Series

Subscribe to GO Classes for GATE CSE 2024

Quick search syntax

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true

Recent Posts

Post GATE 2024 Guidance [Counseling tips and resources]
GATE CSE 2024 Result Responses
[Project Contest] Pytorch backend support for MLCommons Cpp Inference implementation
Participating in MLCommons Inference v4.0 submission (deadline is February 23 12pm IST)
IIITH PGEE 2024 Test Series by GO Classes

Subjects

All categories
General Aptitude (3.5k)
Engineering Mathematics (10.4k)
Digital Logic (3.6k)
Programming and DS (6.2k)
Algorithms (4.8k)
Theory of Computation (6.9k)
Compiler Design (2.5k)
Operating System (5.2k)
Databases (4.8k)
CO and Architecture (4.0k)
Computer Networks (4.9k)
Artificial Intelligence (79)
Machine Learning (48)
Data Mining and Warehousing (25)
Non GATE (1.4k)
Others (2.7k)
Admissions (684)
Exam Queries (1.6k)
Tier 1 Placement Questions (17)
Job Queries (80)
Projects (11)
Unknown Category (870)

64.3k questions

77.9k answers

244k comments

80.0k users

Recent Blog Comments

category ?
Hi @Arjun sir, I have obtained a score of 591 in ...
download here
Can you please tell about IIT-H mtech CSE self...
Please add your admission queries here:...

Send feedback
Rank Predictor
College Prediction
Useful Links
FAQ
Corrections
Discuss
Copyright
Request
Testimonials
Chat Logs
Chat
Badges
Search tips
Exam Category
Blog Category
Blog Tags
Privacy
Test Series
GATER
Refund Policy
Terms and Conditions
Contact Us

Developed by Chun

Twitter WhatsApp Facebook Reddit LinkedIn Email

Link Copied!