Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.

Sign up to join this community
Anybody can ask a question
Anybody can answer
The best answers are voted up and rise to the top
Theoretical Computer Science

Explore our questions

Ask Question
more tags
Active Hot Week Month
1 vote
0 answers
66 views

Tractability of computing generalized hypertreewidth on bounded arity hypergraphs

a3nm's user avatar
a3nm
  • 8,846
1 vote
1 answer
86 views

Efficient Algorithm for Partitioning a Directed Acyclic Graph into Short Paths

Community's user avatar
CommunityBot
  • 1
1 vote
0 answers
62 views

Generalization of the Hamiltonian path problem on Grid Graphs

TRP's user avatar
TRP
  • 31
2 votes
4 answers
6k views

Complexity of greedy coloring

Markus's user avatar
Markus
  • 1
0 votes
0 answers
81 views

5-color graph and minor

Mario Giambarioli's user avatar
Mario Giambarioli
  • 191
2 votes
1 answer
60 views

Upper Bound for distance-two chromatic number in terms of maximum degree

a3nm's user avatar
a3nm
  • 8,846
1 vote
0 answers
31 views

Application LCL definition to vertex coloration

Qise's user avatar
Qise
  • 111
4 votes
1 answer
83 views

Independent set queries with preprocessing

Laakeri's user avatar
Laakeri
  • 1,716
1 vote
1 answer
46 views

What is known about the complexity of Network Diversion?

Laakeri's user avatar
Laakeri
  • 1,716
0 votes
1 answer
57 views

What's the exact complexity of a DFS if we revisit nodes?

Command Master's user avatar
Command Master
  • 465
3 votes
1 answer
134 views

Approximative counting of matchings in a graph

acrendic's user avatar
acrendic
  • 11
3 votes
1 answer
179 views

What is the treewidth of the 3D-grid (mesh or lattice) with sidelength n?

Laakeri's user avatar
Laakeri
  • 1,716
1 vote
1 answer
199 views

Graph partitioning to minimize sum of intra-partition edge weights

Community's user avatar
CommunityBot
  • 1
1 vote
0 answers
44 views

Notion between connected and strongly connected graphs

Cyriac Antony's user avatar
Cyriac Antony
  • 1,703
Browse more Questions

Your privacy

By clicking “Accept all cookies”, you agree Stack Exchange can store cookies on your device and disclose information in accordance with our Cookie Policy.