<we><edit> <!-- questions and answers -->
planar-graphs
matching
quantum-information
reference-request
graph-colouring
pl.programming-languages
polynomials
physics
optimization
oracles
cr.crypto-security
permutations
regular-language
application-of-theory
conditional-results
graph-theory
lambda-calculus
type-systems
coding-theory
ct.category-theory
open-problem
spectral-graph-theory
space-bounded
np-complete
soft-question
graph-theory
Are equally weighted MSTs closely related?
graph-theory
spanning-tree
size of the induced matching
graph-theory
matching
Space efficient "industrial" unbalanced expanders
graph-theory
derandomization
expanders
Maximum weight non-overlapping paths in a DAG
graph-theory
max-flow-min-cut
Minimum cut on a directed graph with negative term
graph-theory
max-flow-min-cut
Minimal Cost of Eulerian Path
ds.algorithms
graph-theory
graph-algorithms
optimization
Why do spectral ultrasparsifiers need to be trees
graph-theory
linear-algebra
spectral-graph-theory
linear-equations
Counting the number of connected components in a dynamic plane graph
graph-theory
graph-algorithms
planar-graphs
An alternative formulation of max flow problem
graph-theory
linear-programming
max-flow-min-cut
max-flow
multicommodity-flow
Why isn't the Charikar algorithm for finding the densest subgraph optimal?
graph-theory
graph-algorithms
approximation
Unbalanced connected partition
graph-theory
graph-algorithms
approximation-algorithms
partition-problem
What are graph grammars?
graph-theory
graph-algorithms
fl.formal-languages
grammars
How can i draw a general resource graph which cannot be completely reduced but which is free from deadlock?
graph-theory
Is a k-connected graph also k-1 connected?
graph-theory
Bounding size of separators when in-degree/out-degree is small?
graph-theory
directed-acyclic-graph
treewidth
Vertex deletion to perfect matching
ds.algorithms
graph-theory
graph-algorithms
fixed-parameter-tractable
Data structure to search name of files and get its path
graph-theory
optimization
ds.data-structures
FOL sentence encoding acyclic graphs using only universal quantifiers
graph-theory
lo.logic
directed-acyclic-graph
first-order-logic
Random Deterministic Automata
graph-theory
automata-theory
pr.probability
Flow Optimization: minimum cost matching of demands from multiple sinks
graph-theory
optimization
max-flow-min-cut
primal-dual
multicommodity-flow
For any two non-isomorphic graphs $G, H$, does there exist a polysize, polylog quantifier depth first order formula which witnesses this?
graph-theory
graph-isomorphism
formulas
first-order-logic
Properties of toroidal graph
reference-request
graph-theory
graph-minor
topological-graph-theory
Common terminology used for lower/upper bounds
graph-theory
approximation-algorithms
optimization
lower-bounds
upper-bounds
Is there any good and free Introduction to topological graph theory
reference-request
graph-theory
co.combinatorics
survey
topological-graph-theory
Girth of graphs that decompose into two disjoint union of spanning trees
graph-theory
girth
spanning-tree
Complexity of finding semi-ordered Eulerian tours in a 4-regular graph
graph-theory
graph-algorithms
time-complexity
Minimum path edge-cover or minimum flow with unit capacities and DAGs
ds.algorithms
graph-theory
max-flow
One Generalization of Graph Isomorphism Problem
graph-theory
graph-algorithms
graph-isomorphism
Determining ties in random network centrality rankings?
graph-theory
graph-algorithms
Bipartite matching with degree domination
graph-theory
matching
Preference based group generator
ds.algorithms
graph-theory
Algorithm finding path with maximal ratio of white vertices
graph-theory
graph-algorithms
Complexity of listing all minimal cut sets / connected 2-partitions of a graph
graph-theory
Application of graph theory in computer science
graph-theory
co.combinatorics
big-list
application-of-theory
Ant colony optimization for traveling salesman problem with changing graph-nodes/vertices
ds.algorithms
graph-theory
tsp
heuristics
Minor and subdivision
graph-theory
graph-minor
Decomposition of edges of eulerian graph into maximum number of cycles
graph-theory
graph-algorithms
Best Hamiltonian Cycle Problem solver
graph-theory
hamiltonian-paths
Graceful labeling completion problems
cc.complexity-theory
reference-request
graph-theory
Optimizing Maximum Weighted Matching (Edmonds Blossom)
ds.algorithms
graph-theory
graph-algorithms
optimization
matching
Complexity consequence of logarithmic boolean width of co-bounded degree graphs?
cc.complexity-theory
graph-theory
graph-algorithms
Book/ Monograph on graph minor theory [Reference request]
reference-request
graph-theory
graph-minor
Transitive Closure of Weighted Random Graphs?
graph-theory
graph-algorithms
transitive-closure
The algebraic connectivity of graphs with large isoperimetric number
graph-theory
spectral-graph-theory
Finding k shortest Paths with Eppstein's Algorithm
ds.algorithms
graph-theory
graph-algorithms
directed-acyclic-graph
Directed graph with bounded in-deg can be partitioned in a balanced way
graph-theory
co.combinatorics
pr.probability
randomized-algorithms
combinatorics
Almost regular subhypergraph of hypergraph with large minimal degree
graph-theory
co.combinatorics
matching
hypergraphs
discrepancy
Modifying Edmonds' Blossom Algorithm
ds.algorithms
graph-theory
graph-algorithms
optimization
Clique cover problem
graph-theory
graph-algorithms
np-hardness
approximation-algorithms
Graph factors of maximum weight
ds.algorithms
graph-theory
graph-algorithms
matching
What is known about counting bipartite perfect matching with average degree in $[2,3]$ and max degree $3$?
ds.algorithms
graph-theory
counting-complexity
permanent
bipartite-graphs
Existence of $d$-regular expander graph that can be represented as a bipartite graph
graph-theory
co.combinatorics
expanders
well-behaved outerplanar
graph-theory
reference clarification: Whitney's theorem on unique embeddability of 3-connected planar graphs?
reference-request
graph-theory
planar-graphs
ho.history-overview
Counting xyz-graphs in $\mathbb{Z}_n^3$
graph-theory
co.combinatorics
lower-bounds
hypergraphs
Lower bound on the largest restrained cubic subset
graph-theory
lower-bounds
hypergraphs
Graph rewriting with one-to-many pattern matching?
graph-theory
pl.programming-languages
term-rewriting-systems
Consequences of $\oplus \mathbf{P} \subseteq \mathbf{NP}$
cc.complexity-theory
graph-theory
complexity-classes
sat
counting-complexity
A conceptual question regarding hardness proofs by reduction
graph-theory
graph-algorithms
np-hardness
reductions
complexity-theory
Efficient update of reachable set of a node in a digraph
ds.algorithms
graph-theory
graph-algorithms
Graphs for which the number of shortest paths between every pair of vertices is polynomially bounded
reference-request
graph-theory
Is this vertex ordering optimization NP-Hard?
graph-theory
np-hardness
Graph addition chains
ds.algorithms
reference-request
graph-theory
co.combinatorics
treewidth
How to partition a graph while minimizing the count of intra-edges?
graph-theory
graph-algorithms
approximation-algorithms
graph-colouring
partition-problem
limit the total flow for some edges in an directed graph
graph-theory
network-modeling
Pathwidth of planarized drawing of $K_{3,n}$
graph-theory
co.combinatorics
graph-drawing
Hadwiger number under matching contraction
graph-theory
graph-minor
Increasing the capacity to maximize the min cut
ds.algorithms
graph-theory
co.combinatorics
max-flow-min-cut
Vertex Cover applications in the real world
ds.algorithms
graph-theory
graph-algorithms
Log space algorithms for modular decomposition tree
cc.complexity-theory
ds.algorithms
reference-request
graph-theory
graph-algorithms
Reachability in Dynamic Line Graph
ds.algorithms
graph-theory
graph-algorithms
ds.data-structures
Maximal non-reducible vertex cover of a graph
graph-theory
graph-algorithms
time-complexity
Vertex isoperimetric number of a graph - NP-hard?
reference-request
graph-theory
np-hardness
Can a flow be decomposed in a given number of paths?
graph-theory
Is there a name for graph regions that lie between two nodes?
graph-theory
Path-width and chromatic number
graph-theory
graph-colouring
Can Lexicographic BFS be implemented in logspace?
cc.complexity-theory
graph-theory
graph-algorithms
logspace
How to check whether graph of n vertex contains n/k disjoint k - complete graph by linear programming?
graph-theory
graph-algorithms
linear-programming
What is the connection between moments of Gaussians and perfect matchings of graphs?
graph-theory
pr.probability
matching
st.statistics
Automata : Language Containment, Minimality & Graph Homomorphism
graph-theory
automata-theory
regular-language
dfa
homomorphism
Hard extendability problems
cc.complexity-theory
reference-request
graph-theory
np-hardness
Which are the features of network based on eigenvalue distribution?
graph-theory
linear-algebra
Optimal polynomial time algorithm to determine if a random graph is $k$-colorable
cc.complexity-theory
graph-theory
graph-algorithms
average-case-complexity
An edge partitioning problem on cubic graphs
graph-theory
np-hardness
co.combinatorics
Add a matching to a Hamiltonian path to reduce the max distance between given pairs of vertices
cc.complexity-theory
graph-theory
graph-algorithms
np-hardness
np-complete
Intractability of restricted decomposition of connected bridgeless cubic graphs
cc.complexity-theory
graph-theory
Non-backtracking paths and the zeta function of graphs
graph-theory
linear-algebra
A generalization of edge cover
graph-theory
np-complete
covering-problems
Embedding a graph with specified edge lengths in d-dimensional space
graph-theory
graph-algorithms
embeddings
CSPs with unbounded fractional hypertree width
cc.complexity-theory
graph-theory
hypergraphs
treewidth
csp
Are there interesting graph classes where the treewidth is hard (easy) to compute?
graph-theory
np-hardness
polynomial-time
treewidth
Looking for a list of algorithms that are more efficient for an outerplanar graph than for an arbitrary graph
graph-theory
graph-algorithms
Number of solutions to the biclique cover problem
graph-theory
Computing mTSP in a k-complete weighted graph
graph-theory
graph-algorithms
tsp
What is "Synthetic Network" in Network Science?
graph-theory
network-modeling
What can i learn about a graph about which only certain properties are known
graph-theory
graph-algorithms
planar-graphs
Combinatorial Independent set Algorithms for sub-classes of perfect graphs
ds.algorithms
graph-theory
graph-algorithms
Connectivity of a random regular graph of degree $d$
reference-request
graph-theory
randomness
random-graphs
Is graph automorphism Karp-reducible to graph isomorphism under hidden subgroup representation?
graph-theory
quantum-computing
reductions
graph-isomorphism
quantum-information
Any fast algorithm for minimum cost feedback arc set problem?
ds.data-structures
graph-theory
np-hardness
approximation-algorithms