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
-
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.
-
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.