Conformability is NP-complete even for connected regular graphs of odd order with α(G)=3 and Δ(G)≥|V(G)|/2 via reduction from perfect triangle packing.
Hopcroft and Richard M
7 Pith papers cite this work. Polarity classification is still indexing.
7
Pith papers citing it
citation-role summary
method 1
citation-polarity summary
verdicts
UNVERDICTED 7roles
method 1polarities
use method 1representative citing papers
Denormalized Lorentzian Laurent series are defined and used to prove new bounds for integral flows on DAGs and weight-space dimensions in parabolic sl_{n+1} Verma modules.
Near-tight (2/3-ε) approximation for identical-capacity bottleneck multiple knapsack and (1/2-ε) for arbitrary capacities, with matching inapproximability.
Presents a successive shortest paths scaling algorithm for unit-capacity min-cost flow achieving Õ((nm)^{2/3} log C) time on planar multigraphs via r-divisions and dense distance graphs.
BURY heuristic partitions graph states across QPUs by minimizing maximum matching sizes between partitions, requiring fewer Bell pairs than standard k-partition methods and lowering cut-rank.
PG-Schema validation is NP-complete in combined complexity and PTIME in data complexity; combined complexity becomes PTIME under restricted alternation of type combinations and unions.
Algorithms based on path and channel decomposition for reachability-focused hierarchical drawings of directed graphs, with experiments on bends, crossings, and clarity, running in O(kn+m) time.
citing papers explorer
-
Conformability is NP-complete, even on connected regular graphs
Conformability is NP-complete even for connected regular graphs of odd order with α(G)=3 and Δ(G)≥|V(G)|/2 via reduction from perfect triangle packing.
-
New Bounds for Integer Flows and Verma Modules, via Denormalized Lorentzian Laurent Series
Denormalized Lorentzian Laurent series are defined and used to prove new bounds for integral flows on DAGs and weight-space dimensions in parabolic sl_{n+1} Verma modules.
-
Near-Tight Approximation Algorithms for Bottleneck Multiple Knapsack Problems
Near-tight (2/3-ε) approximation for identical-capacity bottleneck multiple knapsack and (1/2-ε) for arbitrary capacities, with matching inapproximability.
-
Min-Cost Flow in Unit-Capacity Planar Graphs
Presents a successive shortest paths scaling algorithm for unit-capacity min-cost flow achieving Õ((nm)^{2/3} log C) time on planar multigraphs via r-divisions and dense distance graphs.
-
Quantum Hamlets: Distributed Compilation of Large Algorithmic Graph States
BURY heuristic partitions graph states across QPUs by minimizing maximum matching sizes between partitions, requiring fewer Bell pairs than standard k-partition methods and lowering cut-rank.
-
Validation of graph databases against PG-Schema
PG-Schema validation is NP-complete in combined complexity and PTIME in data complexity; combined complexity becomes PTIME under restricted alternation of type combinations and unions.
-
Adventures in Abstraction: Reachability in Hierarchical Drawings
Algorithms based on path and channel decomposition for reachability-focused hierarchical drawings of directed graphs, with experiments on bends, crossings, and clarity, running in O(kn+m) time.