Explore our questions

1 vote
0 answers
14 views

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

1 vote
0 answers
61 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
53 views

Question about claw-free graphs

12 votes
2 answers
689 views

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

3 votes
1 answer
74 views

What is the fastest algorithm for computing exact network reliability?

1 vote
0 answers
29 views

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

3 votes
2 answers
164 views

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

3 votes
1 answer
348 views

Dynamic transitive closure with immediate new reachability facts

1 vote
1 answer
137 views

Efficient Algorithm for Partitioning a Directed Acyclic Graph into Short Paths

2 votes
0 answers
37 views

Hardness of Coloring based on a Black-Box Hardness of Independent Set

2 votes
1 answer
197 views

Are there any implementations of a graph crossing algorithm?

3 votes
1 answer
305 views

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

2 votes
1 answer
92 views

Maximum cardinality disjoint cycle cover in undirected graphs

0 votes
0 answers
40 views

Minimum spanning tree with only edge ordering

Browse more Questions