Network realignment complexes over arbitrary connected graphs admit an equivariant deformation retraction onto a complete graph plus discrete space; for complete graphs, diameter bounds and Aut(X_n) ≅ S_n (n≥5) are established.
Diestel, Graph Theory, Graduate Texts in Mathematics (Springer Berlin Heidelberg, ed
10 Pith papers cite this work, alongside 55 external citations. Polarity classification is still indexing.
10
Pith papers citing it
55
external citations · OpenAlex
citation-role summary
background 2
citation-polarity summary
roles
background 2polarities
background 2representative citing papers
KLX is the min-max congestion of open back edges over DFS traversals; graphs with KLX at most 2 are fully characterized with linear-time recognition, any graph has tree-width at most KLX+1, and KLX ≤ k is MSO2-expressible hence linear-time decidable for fixed k.
Scalable IP formulations for optimal vertex elimination allow heuristic benchmarking on medium graphs and deliver a parameterized approximation algorithm plus first lower bounds.
Capacitated Vertex Cover admits no k^{o(k)} n^{O(1)} algorithm under ETH, n^{O(tw)} is optimal even for tree-depth, and vertex integrity admits a vi^{O(vi^2)} n^{O(1)} algorithm via N-fold IP.
Additive εn²-approximation for graph edit distance on VC-dimension-d graphs in n^{O(d/ε²)} time, with extensions to quadratic assignment problems and a Weisfeiler-Leman dimension bound for robust graph isomorphism.
Defines the untangling number for 3-periodic tangles and proves that ground states for infinite open curves are crystallographic rod packings.
Constructs and proves correct a QUBO Hamiltonian H_mod,k whose zero-energy ground states exist exactly when a graph admits a nowhere-zero Z_k-flow, with degeneracy matching the flow polynomial.
In combinatorially sphere-like ranked posets of rank k where rank-(k-2) elements have even covering degree, the maximal elements admit a proper 2-coloring.
Infant daily visual experiences of objects are dominated by repeated instances of few exemplars in lumpy similarity clusters, enabling category generalization from small training sets in computational models.
In finite-depth random linear optical circuits, entanglement grows at most diffusively and robust circuit complexity scales similarly, with depth bounds ensuring near-maximal subsystem entanglement and closeness to Haar unitaries.
citing papers explorer
-
Network Realignment Complexes over General Graphs
Network realignment complexes over arbitrary connected graphs admit an equivariant deformation retraction onto a complete graph plus discrete space; for complete graphs, diameter bounds and Aut(X_n) ≅ S_n (n≥5) are established.
-
A Congestion Parameter for Depth-First Graph Traversals
KLX is the min-max congestion of open back edges over DFS traversals; graphs with KLX at most 2 are fully characterized with linear-time recognition, any graph has tree-width at most KLX+1, and KLX ≤ k is MSO2-expressible hence linear-time decidable for fixed k.
-
A Comprehensive Evaluation of Vertex Elimination Algorithms for Algorithmic Differentiation
Scalable IP formulations for optimal vertex elimination allow heuristic benchmarking on medium graphs and deliver a parameterized approximation algorithm plus first lower bounds.
-
Parameterized Capacitated Vertex Cover Revisited
Capacitated Vertex Cover admits no k^{o(k)} n^{O(1)} algorithm under ETH, n^{O(tw)} is optimal even for tree-depth, and vertex integrity admits a vi^{O(vi^2)} n^{O(1)} algorithm via N-fold IP.
-
Robust Graph Isomorphism, Quadratic Assignment and VC Dimension
Additive εn²-approximation for graph edit distance on VC-dimension-d graphs in n^{O(d/ε²)} time, with extensions to quadratic assignment problems and a Weisfeiler-Leman dimension bound for robust graph isomorphism.
-
The untangling number of 3-periodic tangles
Defines the untangling number for 3-periodic tangles and proves that ground states for infinite open curves are crystallographic rod packings.
-
A QUBO Formulation for Nowhere-Zero $k$-Flows
Constructs and proves correct a QUBO Hamiltonian H_mod,k whose zero-energy ground states exist exactly when a graph admits a nowhere-zero Z_k-flow, with degeneracy matching the flow polynomial.
-
$2$-colourability of the maximum ranked elements of a combinatorially sphere-like ranked poset
In combinatorially sphere-like ranked posets of rank k where rank-(k-2) elements have even covering degree, the maximal elements admit a proper 2-coloring.
-
A solution to generalized learning from small training sets found in infant repeated visual experiences of individual objects
Infant daily visual experiences of objects are dominated by repeated instances of few exemplars in lumpy similarity clusters, enabling category generalization from small training sets in computational models.
-
Entanglement and circuit complexity in finite-depth random linear optical networks
In finite-depth random linear optical circuits, entanglement grows at most diffusively and robust circuit complexity scales similarly, with depth bounds ensuring near-maximal subsystem entanglement and closeness to Haar unitaries.