Skip to main content

Explore our questions

12 votes
1 answer
2k views

Is the 3-coloring problem NP-hard on graphs of maximal degree 3?

0 votes
0 answers
32 views

Enhancing a bipartite perfect matching solution with 1-to-2 matchings

3 votes
1 answer
370 views

Dynamic transitive closure with immediate new reachability facts

3 votes
2 answers
890 views

Max flow: either saturate an edge or avoids

4 votes
1 answer
367 views

How do you achieve linear time complexity of greedy graph coloring?

3 votes
0 answers
47 views

Cuthill - Mckee Guarantees?

0 votes
1 answer
28 views

How can I optimize the assignment of object sets to workers with pre-existing caches to minimize discrepancy?

2 votes
1 answer
33 views

Find the weighted perfect "1-to-k" matching algorithm with minimum aggregated k max weight

1 vote
0 answers
68 views

Is there any augmenting graph algorithm available for finding maximum independent set problem in K1,4-free graph in polynomial time

0 votes
1 answer
56 views

Question about claw-free graphs

12 votes
2 answers
697 views

Problems that are NP-Complete when restricted to graphs of treewidth 2 but polynomial on trees

3 votes
1 answer
76 views

What is the fastest algorithm for computing exact network reliability?

1 vote
0 answers
32 views

How can one find a r-division of a graph with strongly sublinear separation profile (separable graphs)?

3 votes
2 answers
168 views

Given a weighted graph with $pk$ nodes find a min weight forest with $p$ components each containing exactly $k$ nodes

Browse more Questions