Paths, Trees, and Flowers
From MaRDI portal
Publication:5341586
DOI10.4153/CJM-1965-045-4zbMath0132.20903OpenAlexW4233756358WikidataQ55920169 ScholiaQ55920169MaRDI QIDQ5341586
Publication date: 1965
Published in: Canadian Journal of Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.4153/cjm-1965-045-4
Related Items
Edge-disjoint packings of graphs, A graph approximation heuristic for the vertex cover problem on planar graphs, The real truth about star designs, Neighbour-sum-2-distinguishing edge-weightings: doubling the 1-2-3 conjecture, On variants of vertex geography on undirected graphs, Maximum number of disjoint paths connecting specified terminals in a graph, Minimum cost perfect matching with delays for two sources, Sum-of-squares rank upper bounds for matching problems, Constant factor approximation for the weighted partial degree bounded edge packing problem, Some Ore-type results for matching and perfect matching in \(k\)-uniform hypergraphs, On the complexity of some basic problems in computational convexity. I. Containment problems, The matching relaxation for a class of generalized set partitioning problems, Some complete and intermediate polynomials in algebraic complexity theory, A lower bound on the acyclic matching number of subcubic graphs, Circular convex bipartite graphs: Maximum matching and Hamiltonian circuits, An NC algorithm for the clique cover problem in cocomparability graphs and its application, On renamable Horn and generalized Horn functions, On the linear \(k\)-arboricity of cubic graphs, Claw-free graphs---a survey, The stochastic stability of decentralized matching on a graph, Computational comparison of several greedy algorithms for the minimum cost perfect matching problem on large graphs, Interior-point methods: An old and new approach to nonlinear programming, The \(\beta\)-assignment problem in general graphs, A combinatorial column generation algorithm for the maximum stable set problem, Block triangularization of skew-symmetric matrices, The delta-sum of matching delta-matroids, Sampling weighted perfect matchings on the square-octagon lattice, Finding independent sets in \(K_4\)-free 4-regular connected graphs, Graph theoretic relaxations of set covering and set partitioning problems, A \(0(| V | \cdot | E |)\) algorithm for maximum matching of graphs, Colouring squares of claw-free graphs, \(d\)-matching in 3-uniform hypergraphs, On the graphic matroid parity problem, Small maximal matchings in random graphs., On the construction of graphs with a planar bipartite double cover from Boolean formulas and its application to counting satisfying solutions, A compact linear program for testing optimality of perfect matchings., Struction revisited, Maximum matchings in regular graphs, Graphs vertex-partitionable into strong cliques, Global constraints for round robin tournament scheduling., Restricted assignment scheduling with resource constraints, Relations between the lower domination parameters and the chromatic number of a graph., Bargaining in a network of buyers and sellers., Overlays with preferences: distributed, adaptive approximation algorithms for matching with preference lists, Natalie 2.0: sparse global network alignment as a special case of quadratic assignment, Parameterized algorithms and kernels for rainbow matching, The matching extension problem in general graphs is co-NP-complete, On retracts, absolute retracts, and foldings in cographs, Finding a maximum 2-matching excluding prescribed cycles in bipartite graphs, How (not) to integrate blood subtyping technology to kidney exchange, Integer programming formulations for the minimum weighted maximal matching problem, A set partitioning approach to shunting, Minimum-weight perfect matching for nonintrinsic distances on the line, Systems of distant representatives, The lattice dimension of a graph, Generalized subgraph-restricted matchings in graphs, Linear algorithms for testing the sign stability of a matrix and for finding Z-maximum matchings in acyclic graphs, Vertex colorings without isolates, On the (parameterized) complexity of recognizing well-covered (\(r\),\(\ell\))-graph, Efficient Algorithms for (3,1) Graphs, The dependence graph for bases in matroids, Testing for Equality between Maximum Matching and Minimum Node Covering, Hamilton cycles in hypergraphs below the Dirac threshold, Maximum colorful independent sets in vertex-colored graphs, A remark on the time complexity of the subtree problem, The distribution of 1-widths of (0,1)-matrices, On classes of relations and graphs determined by subobjects and factorobjects, A polynomial kernel for trivially perfect editing, Stabilizing network bargaining games by blocking players, On improving matchings in trees, via bounded-length augmentations, Independence numbers of graphs - an extension of the Koenig-Egervary theorem, On Reid's characterization of the ternary matroids, An identity for matching and skew-symmetric determinant, On the minors of an incidence matrix and Smith normal form, Matchings and covers in hypergraphs, Solving the linear matroid parity problem as a sequence of matroid intersection problems, Transportation networks: Old and new, The optimal path-matching problem, Covering a symmetric poset by symmetric chains, ``Global graph problems tend to be intractable, A simple linear expected time algorithm for finding a Hamilton path, Toughness and matching extension in graphs, König-Egerváry graphs, 2-bicritical graphs and fractional matchings, On the algorithmic complexity of twelve covering and independence parameters of graphs, Graphs with no \(M\)-alternating path between two vertices, On the factorization of graphs with exactly one vertex of infinite degree, Randomised algorithms, Perfect stables in graphs, On the number of 1-factors of locally finite graphs, Adjacency on combinatorial polyhedra, Spanning subgraphs with specified valencies, Duality theorems for finite structures (characterising gaps and good characterisations), Disconnected 2-factors in planar cubic bridgeless graphs, A primal dual integer programming algorithm, On the \(k\)-systems of a simple polytope, A 2-approximation algorithm for the minimum weight edge dominating set problem, A greedy heuristic for a minimum-weight forest problem, Confinement-Higgs transition in a disordered gauge theory and the accuracy threshold for quantum memory, Relaxed tours and path ejections for the traveling salesman problem, A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm, Tractability in constraint satisfaction problems: a survey, Two function algebras defining functions in \(\mathsf{NC}^k\) Boolean circuits, Optimum distance flag codes from spreads via perfect matchings in graphs, Traveling salesman problems in temporal graphs, Augmenting approach for some maximum set problems, A \((2 + \epsilon ) k\)-vertex kernel for the dual coloring problem, Hierarchical \(b\)-matching, Counting induced subgraphs: an algebraic approach to \(\#\)W[1-hardness], Additive approximation of generalized Turán questions, Euclidean maximum matchings in the plane -- local to global, A query-efficient quantum algorithm for maximum matching on general graphs, Parallel approximation algorithms for maximum weighted matching in general graphs, The difference between the metric dimension and the determining number of a graph, Gallai-Edmonds decomposition as a pruning technique, Computing equilibria: a computational complexity perspective, Scheduling arc shut downs in a network to maximize flow over time with a bounded number of jobs per time period, Deterministic versus randomized adaptive test cover, Incremental assignment problem, Graph factors and factorization: 1985--2003: a survey, Computational complexity of the semantics of some natural language constructions, On the maximum even factor in weakly symmetric graphs, A characterization of the graphs in which the transversal number equals the matching number, Excessive factorizations of bipartite multigraphs, Induced graph packing problems, König-Egerváry graphs are non-Edmonds, Maximum matching in multi-interface networks, Induced matchings in subcubic graphs without short cycles, Matchings in graphs of odd regularity and girth, Approximation with a fixed number of solutions of some multiobjective maximization problems, On vertex independence number of uniform hypergraphs, Altruistically unbalanced kidney exchange, On the recognition of fuzzy circular interval graphs, Jenő Egerváry: from the origins of the Hungarian algorithm to satellite communication, Exact algorithms for dominating set, Editing graphs to satisfy degree constraints: a parameterized approach, Lower and upper bounds for the \(m\)-peripatetic vehicle routing problem, Partitioning planar graphs: a fast combinatorial approach for max-cut, Tree search and quantum computation, A short proof of the Berge-Tutte formula and the Gallai-Edmonds structure theorem, Nash-solvable two-person symmetric cycle game forms, A simple reduction from maximum weight matching to maximum cardinality matching, FPT algorithms for path-transversal and cycle-transversal problems, Combinatorial and computational aspects of graph packing and graph decomposition, Randomly colouring graphs (a combinatorial view), Colouring graphs when the number of colours is almost the maximum degree, On matching cover of graphs, Certifying algorithms, Optimizing regenerator cost in traffic grooming, Polynomial-time perfect matchings in dense hypergraphs, The complexity of the zero-sum 3-flows, Distributed algorithms for covering, packing and maximum weighted matching, Exploring the tractability border in epistemic tasks, A superlocal version of Reed's conjecture, Per-spectral characterizations of graphs with extremal per-nullity, Simulated versus reduced noise quantum annealing in maximum independent set solution to wireless network scheduling, Approximate triclique coloring for register allocation, Counting the number of perfect matchings in \(K_{5}\)-free graphs, Two complexity results for the vertex coloring problem, Nash equilibria in the two-player kidney exchange game, On paths avoding forbidden pairs of vertices in a graph, Bond graphs. II: Causality and singularity, Greedy matching: guarantees and limitations, Packings and perfect path double covers of maximal planar graphs, Minimum vertex weighted deficiency of \((g,f)\)-factors: A greedy algorithm, A generalized hypergreedy algorithm for weighted perfect matching, Finite-model theory -- A personal perspective, Graph editing problems with extended regularity constraints, Efficient stabilization of cooperative matching games, Kidney exchange: an egalitarian mechanism, A kernel of order \(2k - c\) for Vertex Cover, My experiences as a student and researcher in OR during the 1960's and 70's, Strongly linear trend-free block designs and 1-factors of representative graphs, Augmenting graphs for independent sets, Reconstructing polygons from scanner data, On average lower independence and domination numbers in graphs, A combinatoric interpretation of dual variables for weighted matching and \(f\)-factors, A new analysis of a self-stabilizing maximum weight matching algorithm with approximation ratio 2, Two easy duality theorems for product partial orders, A min-max relation for stable sets in graphs with no odd-\(K_ 4\), Spanning trees of 3-uniform hypergraphs, Simulating the impact of crossover kidney transplantation on the Nord Italia transplant program, Maximum induced matching of hexagonal graphs, Heuristics for the mixed swapping problem, Blossom V: A new implementation of a minimum cost perfect matching algorithm, \(b\)-coloring is NP-hard on co-bipartite graphs and polytime solvable on tree-cographs, Alternating Whitney sums and matchings in trees. II, The perfectly matchable subgraph polytope of an arbitrary graph, Packing paths perfectly, A note on the separation problem for the matching matroid, Induced packing of odd cycles in planar graphs, Combinatorial optimization with 2-joins, On matroid parity and matching polytopes, Spectral aspects of symmetric matrix signings, A characterization of König-Egerváry graphs with extendable vertex covers, Critical graphs, matchings and tours or a hierarchy of relaxations for the travelling salesman problem, A partitioning algorithm for minimum weighted Euclidean matching, A comparison of heuristics and relaxations for the capacitated plant location problem, Pairwise kidney exchange, A degree sequence Hajnal-Szemerédi theorem, Fast algorithms for the undirected negative cost cycle detection problem, t-expansive and t-wise intersecting hypergraphs, On the existence of weak greedy matching heuristics, Eine Min-Max Beziehung für das Exakte Matroid Problem. (A min-max relation for the exact matroid problem), Even cycles in directed graphs, Maximal tight sets and the Edmonds-Gallai decomposition for matchings, An augmenting path algorithm for linear matroid parity, Algorithms for finding k-best perfect matchings, Maximum matchings in a class of random graphs, Matching is as easy as matrix inversion, On the maximum 2-1 matching, Fractional matchings and the Edmonds-Gallai theorem, Minimum-maximal matching in series-parallel graphs, Undirected distances and the postman-structure of graphs, A Las Vegas RNC algorithm for maximum matching, The general maximum matching algorithm of Micali and Vazirani, Alternating Whitney sums and matchings in trees. 1, On matroids induced by packing subgraphs, A polynomial algorithm for b-matchings: An alternative approach, Edge-colouring random graphs, Edge-disjoint in- and out-branchings in tournaments and related path problems, Matching structure and the matching lattice, Matchings in simplicial complexes, circuits and toric varieties, Combinatorial algorithms for matchings, even factors and square-free 2-factors, Penelope's graph: a hard minimum cost tension instance, A generalized Hungarian method for solving minimum weight perfect matching problems with algebraic objective, On maximal independent sets of vertices in claw-free graphs, Fast probabilistic algorithms for Hamiltonian circuits and matchings, Matroid matching and some applications, Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé, f-factors and related decompositions of graphs, Subgraphs and their degree sequences of a digraph, Independence systems with continuous cardinality of bases, On generalized matching problems, Approximating the bottleneck plane perfect matching of a point set, Algorithmic proofs of two relations between connectivity and the 1- factors of a graph, Real-time scheduling to minimize machine busy times, A new linear programming algorithm - better or worse than the simplex method?, Matchings in regular graphs, An efficient distributed algorithm for maximum matching in general graphs, Complexity-theoretic algebra. II: Boolean algebras, Matchings and \(\Delta\)-matroids, Blocking systems of a graph and intersection-union interchange equality in bottleneck problems involving sets and fuzzy sets, Packing subgraphs in a graph, Unlikelihood that minimal phylogenies for a realistic biological study can be constructed in reasonable computational time, Approximation algorithms for partially covering with edges, Turing machines and bimachines, Hardness of optimal spaced seed design, Approximation of satisfactory bisection problems, Simultaneous matchings: Hardness and approximation, Compact systems for T-join and perfect matching polyhedra of graphs with bounded genus, Saturation number of fullerene graphs, An introduction to randomized algorithms, A structure theorem for maximum internal matchings in graphs, Euclidean semi-matchings of random samples, Minimum spectral radius of a weighted graph, Partition into cliques for cubic graphs: Planar case, complexity and approximation, A weighted even factor algorithm, Clique-circulants and the stable set polytope of fuzzy circular interval graphs, The stable set polytope of quasi-line graphs, George Dantzig's impact on the theory of computation, Extremal perfect graphs for a bound on the domination number, On complexity of special maximum matchings constructing, Solving combinatorial optimization problems using Karmarkar's algorithm, On finding augmenting graphs, Matching theory -- a sampler: From Dénes König to the present, Structural properties of matroid matchings, Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles, Covering graphs with matchings of fixed size, Structural analysis of a fractional matching problem, Elementary graphs with respect to \(f\)-parity factors, Finding a maximum matching in a circular-arc graph, Maximum independent sets in subclasses of \(P_{5}\)-free graphs, Distances in orientations of graphs, Covers, matchings and odd cycles of a graph, Satisfactory graph partition, variants, and generalizations, Maximum matching and the game of Slither, Acyclic orientations of a graph and the chromatic and independence numbers, An introduction to matching polynomials, The labeled maximum matching problem, Good characterizations for some degree constrained subgraphs, Finding augmenting chains in extensions of claw-free graphs, Stabilizing maximum matching in bipartite networks, Packing trees with constraints on the leaf degree, Random assignment under weak preferences, Independent sets in bounded-degree hypergraphs, Using clausal graphs to determine the computational complexity of \(k\)-bounded positive one-in-three SAT, Weighted sum coloring in batch scheduling of conflicting jobs, Bounding the size of equimatchable graphs of fixed genus, Blockers and transversals, A surprising permanence of old motivations (a not-so-rigid story), The strong perfect graph conjecture: 40 years of attempts, and its resolution, The method of alternating paths, Ear-decompositions of matching-covered graphs, The Edmonds-Gallai decomposition for matchings in locally finite graphs, Brick decompositions and the matching rank of graphs, On the complexity of partitioning graphs into connected subgraphs, An extension of matching theory, On the complexity of a family of generalized matching problems, Packings by cliques and by finite families of graphs, Maximizing a supermodular pseudoboolean function: A polynomial algorithm for supermodular cubic functions, Polynomial-time approximation algorithms for the coloring problem in some cases, A generalisation of matching and colouring, Graph realizations constrained by skeleton graphs, A new approach on locally checkable problems, An introduction to population approaches for optimization and hierarchical objective functions: A discussion on the role of tabu search, Conservative weightings and ear-decompositions of graphs, Maximum matchings in planar graphs via Gaussian elimination, Characterization of saturated graphs related to pairs of disjoint matchings, A travelling salesman approach to solve the \(F\)/no-idle/\(C_{max}\) problem, Adaptive paired comparison design, New primal and dual matching heuristics, Approximate generalized matching: \(f\)-matchings and \(f\)-edge covers, Finding a maximum matching in a permutation graph, Adaptive approximation models in optimization, What would Edmonds do? Augmenting paths and witnesses for degree-bounded MSTs, More aspects of arbitrarily partitionable graphs, Maximum 0-1 timed matching on temporal graphs, A primal-dual approximation algorithm for \textsc{minsat}, Revisiting a cutting-plane method for perfect matchings, On some domination colorings of graphs, On approximability of optimization problems related to red/blue-split graphs, Approximating activation edge-cover and facility location problems, Erdős-Ko-Rado for perfect matchings, A one-sided many-to-many matching problem, A short algorithm to delete singular junctions in bond graphs, From matchings to independent sets, At most \(k\)-to-1 mappings between graphs. II, The (theta, wheel)-free graphs. III: Cliques, stable sets and coloring, On the complexity of solving feasible systems of linear inequalities specified with approximate data, Co-density and fractional edge cover packing, On the lattices of NP-subspaces of a polynomial time vector space over a finite field, Irreducible decomposition of powers of edge ideals, Market sentiments and convergence dynamics in decentralized assignment economies, 3-colouring AT-free graphs in polynomial time, A polynomial-time algorithm of finding a minimum \(k\)-path vertex cover and a maximum \(k\)-path packing in some graphs, Maximizing the strong triadic closure in split graphs and proper interval graphs, Null decomposition of unicyclic graphs, A kernel of order \(2k-c\log k\) for vertex cover, Exact algorithms for edge domination, Polyhedron of triangle-free simple 2-matchings in subcubic graphs, Maximum matching in regular and almost regular graphs, On caterpillar factors in graphs, Fair-by-design matching, Reinforcement learning for optimal error correction of toric codes, The roommates problem revisited, On the classification of NP-complete problems in terms of their correlation coefficient, The \(b\)-\textsc{Matching} problem in distance-hereditary graphs and beyond, An improved kernel for max-bisection above tight lower bound, On the Chvátal-Gomory closure of a compact convex set, Lee-Yang theorems and the complexity of computing averages, Largest 2-regular subgraphs in 3-regular graphs, Approximating the length of Chinese postman tours, The complexity of planar Boolean \#CSP with complex weights, Perfect matching in \(k\)-partite \(k\)-graphs and 3-uniform HM-bipartite hypergraphs, Navigating between packings of graphic sequences, Minimum cost stability in exchange networks, Partitioning graphs into induced subgraphs, Dispersing obnoxious facilities on a graph, The complexity of perfect matchings and packings in dense hypergraphs, Temporal matching, Algorithmic aspects of upper edge domination, An Edmonds-Gallai-type decomposition for the \(j\)-restricted \(k\)-matching problem, On the rational polytopes with Chvátal rank 1, On the König deficiency of zero-reducible graphs, Extended formulations for radial cones, A comparison of matching algorithms for kidney exchange programs addressing waiting time, Disjoint dominating and 2-dominating sets in graphs, Quadratic vertex kernel for rainbow matching, Kidney exchange with immunosuppressants, Polynomial size linear programs for problems in \textsc{P}, Detecting strong cliques, Efficient parallel algorithms for parameterized problems, Cooperative games with overlapping coalitions: charting the tractability frontier, Limit theory of combinatorial optimization for random geometric graphs, Computing in combinatorial optimization, Asymptotic connectedness of random interval graphs in a one dimensional data delivery problem, Graft analogue of general Kotzig-Lovász decomposition, Critical paired dominating sets and irreducible decompositions of powers of edge ideals, Minimum cost \(b\)-matching problems with neighborhoods, Atoms of the matching measure, Anisotropic mesh generation and adaptation for quads using the \(L_p\)-CVT method, A theoretical and computational equilibria analysis of a multi-player kidney exchange program, Maximum matching in almost linear time on graphs of bounded clique-width, Easy and difficult exact covering problems arising in VLSI power reduction by clock gating, Oriented Euler complexes and signed perfect matchings, Output sensitive fault tolerant maximum matching, On maximum matchings in 5-regular and 6-regular multigraphs, Zero-visibility cops and robber and the pathwidth of a graph, From one to many rainbow Hamiltonian cycles, Universally balanced combinatorial optimization games, Towards an algorithmic guide to Spiral Galaxies, Computing maximum non-crossing matching in convex bipartite graphs, Efficient recognition of equimatchable graphs, A refined Gallai-Edmonds structure theorem for weighted matching polynomials, Excessive \([l, m\)-factorizations], On partial descriptions of König graphs for odd paths and all their spanning supergraphs, Cycles in complementary prisms, New insights on integer-programming models for the kidney exchange problem, On a generalization of the Chvátal-Gomory closure, Continuous facility location on graphs, Strong product of factor-critical graphs, Packing of graphic n-tuples, The Legacy of Turing in Numerical Analysis, Blossom-Quad: A non-uniform quadrilateral mesh generator using a minimum-cost perfect-matching algorithm, Combinatorics and algorithms for augmenting graphs, Approximation algorithms and heuristics for a 2-depot, heterogeneous Hamiltonian path problem, A Basic Parameterized Complexity Primer, The symmetric travelling salesman problem. I: New fast lower bounds for the problem of optimal 2-matching, Fractional matchings, component-factors and edge-chromatic critical graphs, Clique-perfectness and balancedness of some graph classes, The use of a pruned modular decomposition for \textsc{maximum matching} algorithms on some graph classes, On the complexity of colouring antiprismatic graphs, Colorful edge decomposition of graphs: some polynomial cases, Decomposition theorems for square-free 2-matchings in bipartite graphs, Improved instance generation for kidney exchange programmes, Recovery of disrupted airline operations using \(k\)-maximum matching in graphs, Tropical matchings in vertex-colored graphs, Speeding up Graph Algorithms via Switching Classes, On the hardness of deciding the equality of the induced and the uniquely restricted matching number, Exact and approximate methods for the score-constrained packing problem, On the NP-hardness of deciding emptiness of the split closure of a rational polytope in the 0,1 hypercube, Large rainbow matchings in general graphs, Constant Factor Approximation for the Weighted Partial Degree Bounded Edge Packing Problem, On the (Parameterized) Complexity of Recognizing Well-Covered $$(r,\ell )$$ -graphs, No-Wait Scheduling Problems with Batching Machines, Markovian online matching algorithms on large bipartite random graphs, Crumby colorings -- red-blue vertex partition of subcubic graphs regarding a conjecture of Thomassen, Bayesian locally optimal design of knockout tournaments, Complexity of branch-and-bound and cutting planes in mixed-integer optimization, Quantum memories and error correction, A weighted independent even factor algorithm, Rectangular surface code under biased noise, FPT and kernelization algorithms for the induced tree problem, Temporal matching on geometric graph data, Extremal graphs for a new upper bound on domination parameters in graphs, A fresh look at research strategies in computational cognitive science: the case of enculturated mathematical problem solving, A detailed introduction to a minimum-cost perfect matching algorithm based on linear programming, Linear Time Approximation Algorithms for Degree Constrained Subgraph Problems, How heavy independent sets help to find arborescences with many leaves in DAGs, Pareto optimality in coalition formation, Second kind maximum matching graph, Decision problem for perfect matchings in dense 𝑘-uniform hypergraphs, Linear hypergraphs with large transversal number and maximum degree two, The Time Complexity of the Token Swapping Problem and Its Parallel Variants, How many attackers can selfish defenders catch?, Kidney exchange: further utilization of donors via listed exchange, Packing paths: recycling saves time, Dominating induced matchings in graphs without a skew star, A reduction algorithm for the weighted stable set problem in claw-free graphs, Ordered weighted average combinatorial optimization: formulations and their properties, The Complexity of Perfect Packings in Dense Graphs, Bi-criteria and approximation algorithms for restricted matchings, Parameterized Algorithms for the Independent Set Problem in Some Hereditary Graph Classes, Matchings of cycles and paths in directed graphs, A \(\frac{1}{2}\)-integral relaxation for the \(A\)-matching problem, A characterization of Konig-Egervary graphs using a common property of all maximum matchings, On the Chvátal-Gomory Closure of a Compact Convex Set, Optimal Matching Forests and Valuated Delta-Matroids, Domination When the Stars Are Out, Processor efficient parallel matching, Packing non-returning \(A\)-paths algorithmically, Fractionally total colouring \(G_{n,p}\), Finding thet-join structure of graphs, Oriented star packings, Reductions to 1–matching polyhedra, Augmenting chains in graphs without a skew star., Dynamic matchings and quasidynamic fractional matchings. I, Dynamic matchings and quasidynamic fractional matchings. II, Unnamed Item, A modified greedy algorithm for dispersively weighted 3-set cover, Matching and spanning in certain planar graphs, Edmonds polytopes and a hierarchy of combinatorial problems. (Reprint), Spanning subgraphs with specified valencies. (Reprint), Finding maximum square-free 2-matchings in bipartite graphs, A fault-tolerant one-way quantum computer, A Comprehensive Analysis of Polyhedral Lift-and-Project Methods, The Cutting Plane Method is Polynomial for Perfect Matchings, Exact and Heuristic Algorithms for Capacitated Vehicle Routing Problems with Quadratic Costs Structure, Even factors, jump systems, and discrete convexity, On the Complexity of Computing the Excessive [B-Index of a Graph], Decomposition algorithms for solving the minimum weight maximal matching problem, Maximum internally stable sets of a graph, Complexity Theory Basics: NP and NL, Induced Matchings in Graphs of Bounded Maximum Degree, Heuristically guided search and chromosome matching, $$P\mathop{ =}\limits^{?}NP$$, Decomposition Theorems for Square-free 2-matchings in Bipartite Graphs, Efficient Matching for Column Intersection Graphs, Anti-blocking polyhedra, Establishing the matching polytope, Subsampling in Smoothed Range Spaces, Sum-of-Squares Rank Upper Bounds for Matching Problems, Bestimmung eines maximalen Matching in beliebigen Graphen, Optimal scheduling for two-processor systems, Edmonds polytopes and a hierarchy of combinatorial problems, The Exact Weighted Independent Set Problem in Perfect Graphs and Related Classes, A note on line coverings of graphs, Path problems in skew-symmetric graphs, The 2004 Benjamin Franklin medal in computer and cognitive science presented to Richard M. Karp, Partitioning a graph into two pieces, each isomorphic to the other or to its complement, ON THE MATCHING NUMBER OF AN UNCERTAIN GRAPH, Adjacency on the Postman Polyhedron, Ond-threshold graphs andd-dimensional bin packing, Solving matching problems with linear programming, On Planar Boolean CSP, Factors and factorizations of graphs—a survey, Binary group and Chinese postman polyhedra, Node-Balancing by Edge-Increments, The Price of Matching with Metric Preferences, Euclidean matching problems and the metropolis algorithm, Stabilizing Network Bargaining Games by Blocking Players, Packings by Complete Bipartite Graphs, An Introduction to Temporal Graphs: An Algorithmic Perspective, Scaling: A general framework, Linear-Time Approximation for Maximum Weight Matching, Approximation and Exact Algorithms for Special Cases of Connected f-Factors, A Characterisation of Strict Matching Matroids, Strict matching matroids and matroid algorithms, An efficient heuristic algorithm for minimum matching, Topological quantum memory, Worst-case greedy matchings in the unitd-cube, Independent edges in bipartite graphs obtained from orientations of graphs, Solution of one problem of optimal partition of the vertex set of a hypergraph, A Fast Lower Bound for the Minimum Cost Perfect 2-Matching Linear Program, Geometry Helps to Compare Persistence Diagrams, On the Power of Tree-Depth for Fully Polynomial FPT Algorithms, A Simple Criterion for a Graph to have a Perfect Matching, Polyhedral Combinatorics in Combinatorial Optimization, Unnamed Item, d-matching in k-uniform hypergraphs, Full reduction of a general square matrix, Packing $k$-Matchings and $k$-Critical Graphs, Deep Haar scattering networks, OptimalA PrioriBalance in the Design of Controlled Experiments, Classifying the computational complexity of problems, An algorithmic framework for the matching problem in some hypergraphs, Vertex packings: Structural properties and algorithms, The Time Complexity of Permutation Routing via Matching, Token Swapping and a Variant, Colouring Squares of Claw-free Graphs, On the Complexity of Holant Problems, Shortest alternating path algorithms, The structure of (theta, pyramid, 1‐wheel, 3‐wheel)‐free graphs, An efficient algorithm for minimumk-covers in weighted graphs, Odd Multiway Cut in Directed Acyclic Graphs, Topological quantum error correction in the Kitaev honeycomb model, On Perfect Matchings and Tilings in Uniform Hypergraphs, Fully Dynamic Maximal Matching in $O(\log n)$ Update Time (Corrected Version), Minimizing maximum lateness on one machine: computational experience and some applications, A survey of heuristics for the weighted matching problem, The maximum independent set problem for cubic planar graphs, Lineare Charakterisierungen von Travelling Salesman Problemen, Minimal complete matchings and negative cycles, Unnamed Item, Unnamed Item, A good algorithm for lexicographically optimal flows in multi-terminal networks, Line perfect graphs, The even-path problem for graphs and digraphs, Duality and admissible transformations in combinatorial optimization, The ABACUS system for branch-and-cut-and-price algorithms in integer programming and combinatorial optimization, Polynomial time algorithms for two classes of subgraph problem, The Simple Reachability Problem in Switch Graphs, Una variante del algoritmo de Edmonds para acoplamientos Maximos, Graph Stabilization: A Survey, Approximation algorithms for graph approximation problems, Von Neumann, Gödel and Complexity Theory, Packing paths in digraphs, COMPUTATIONAL COMPLEXITY OF THE PERFECT MATCHING PROBLEM IN HYPERGRAPHS WITH SUBCRITICAL DENSITY, Balanced network flows. III. Strongly polynomial augmentation algorithms, Spanning subgraphs of graphs partitioned into two isomorphic pieces, Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs, Logical error rate scaling of the toric code, Universality, Invariance, and the Foundations of Computational Complexity in the Light of the Quantum Computer, König Graphs with Respect to the 4-Path and Its Spanning Supergraphs, Stabilizing Weighted Graphs, A polynomial algorithm for maximum weighted vertex packings on graphs without long odd cycles, Paths, Stars and the Number Three, Algorithms for Weighted Boolean Optimization, Inhomogeneous graph sorting and job distribution between two processors, Reflections on graph theory, Claw‐Free Graphs, Skeletal Graphs, and a Stronger Conjecture on ω, Δ, and χ, Graph labelings derived from models in distributed computing: A complete complexity classification, Karp–Sipser on Random Graphs with a Fixed Degree Sequence, Rank of maximum matchings in a graph, Optimum matching forests I: Special weights, Sensitivity analysis of optimal matchings, NC Algorithms for Computing a Perfect Matching and a Maximum Flow in One-Crossing-Minor-Free Graphs, Scenario Grouping and Decomposition Algorithms for Chance-Constrained Programs, Counting Weighted Independent Sets beyond the Permanent, A shortest augmenting path method for solving minimal perfect matching problems, Frutex y caminos nodales, Polynomial algorithms for a class of linear programs, Some facets of the simple plant location polytope, Fast and Simple Algorithms for Weighted Perfect Matching, A hypergraph version of the Gallai-Edmonds Theorem, A multicommodity flow problem, Matching, Euler tours and the Chinese postman, Perfect Matching in General vs. Cubic Graphs: A Note on the Planar and Bipartite Cases, A 1-matching blossom-type algorithm for edge covering problems, Polynomial algorithms for estimating network reliability, Optimal set partitioning, matchings and lagrangian duality, Disconnected matchings, Polynomial-delay and polynomial-space enumeration of large maximal matchings, An approximation algorithm for the clustered path travelling salesman problem, Spectral extrema of graphs with bounded clique number and matching number, Average Sensitivity of Graph Algorithms, Blocking trails for \(f\)-factors of multigraphs, Co-degree threshold for rainbow perfect matchings in uniform hypergraphs, Coloring rings, Finding Maximum Edge-Disjoint Paths Between Multiple Terminals, Strict finitism and feasibility, Design methods for 3D wireframe DNA nanostructures, Optimal general factor problem and jump system intersection, Graph and hypergraph colouring via nibble methods: a survey, Gene order phylogeny via ancestral genome reconstruction under Dollo, Arc routing problems: A review of the past, present, and future, Graphical representation and hierarchical decomposition mechanism for vertex-cover solution space, Maximum skew-symmetric flows, Structural parameterizations for equitable coloring: complexity, FPT algorithms, and kernelization, Approximations for the Steiner multicycle problem, Integer programming models for round Robin tournaments, Pairs of disjoint matchings and related classes of graphs, Counterexamples to the characterisation of graphs with equal independence and annihilation number, Polyhedral techniques in combinatorial optimization: matchings and tours, An approximation algorithm for the clustered path travelling salesman problem, Solving maximum weighted matching on large graphs with deep reinforcement learning, A deterministic parallel reduction from weighted matroid intersection search to decision, An improvement on Łuczak's connected matchings method, Socially fair matching: exact and approximation algorithms, Excluding a planar matching minor in bipartite graphs, Parameterized Counting and Cayley Graph Expanders, Efficiently recognizing graphs with equal independence and annihilation numbers, Fully Online Matching with Advice on General Bipartite Graphs and Paths, Weighted connected matchings, Computing maximum matchings in temporal graphs, On the complexity of minimum maximal acyclic matchings, Maximum weight perfect matching problem with additional disjunctive conflict constraints, On new algorithmic techniques for the weighted vertex coloring problem, Approximating minimum weight perfect matchings for complete graphs satisfying the triangle inequality, Approximating the directed path partition problem, Unnamed Item, Diverse Pairs of Matchings, An upper bound on the double Roman domination number, Counting independent sets in graphs with bounded bipartite pathwidth, The clever shopper problem, Recovery of disrupted airline operations using \(k\)-maximum matching in graphs, Online request server matching, Improved approximation algorithms for minimum power covering problems, On three polynomial kernels of sequences for arbitrarily partitionable graphs, Some graph optimization problems with weights satisfying linear constraints, Computing the nucleolus of weighted cooperative matching games in polynomial time, Disconnected matchings, Leafy spanning arborescences in DAGs, An Asymptotic Multipartite Kühn--Osthus Theorem, Minimum Cost Perfect Matching with Delays for Two Sources, Parameterized Complexity of $$(A,\ell )$$-Path Packing, Continuous Facility Location on Graphs, Matching of Given Sizes in Hypergraphs, Sparktope: linear programs from algorithms, Hitting Weighted Even Cycles in Planar Graphs, Saturation of Newton polytopes of type A and D cluster variables, Odd Multiway Cut in Directed Acyclic Graphs, Construction of k-matchings in graph products, Generalized XOR non-locality games with graph description on a square lattice, Minimum weight euclidean matching and weighted relative neighborhood graphs, Excluded $t$-Factors in Bipartite Graphs: Unified Framework for Nonbipartite Matchings, Restricted 2-Matchings, and Matroids, Counting Small Induced Subgraphs Satisfying Monotone Properties, A Local Diagnosis Algorithm for Hypercube-like Networks under the BGM Diagnosis Model, On the König graphs for a 5-path and its spanning supergraphs, Notes on weak-odd edge colorings of digraphs, Coverings and delta-coverings, Data Reduction for Maximum Matching on Real-World Graphs, Popular Matchings with Ties and Matroid Constraints, Clustering in Hypergraphs to Minimize Average Edge Service Time, Unnamed Item, The factorization of graphs. II, On the structure of factorizable graphs, Unnamed Item, Unnamed Item, Blocking and anti-blocking pairs of polyhedra, On König graphs with respect to P4, Using decomposition in integer programming, On the structure of factorizable graphs. II, Hidden Hamiltonian Cycle Recovery via Linear Programming, Round Compression for Parallel Matching Algorithms, Integer Programming Formulations and Benders Decomposition for the Maximum Induced Matching Problem, The role of entropy in topological quantum error correction, Random-link matching problems on random regular graphs, Exploring the Limits of Subadditive Approaches: Parallels between Optimization and Complexity Theory, Universal topological phase of two-dimensional stabilizer codes, Surface code quantum computing by lattice surgery, Direct evaluation of pure graph state entanglement, Lifetime of topological quantum memories in thermal environment, Fast decoders for qudit topological codes, Approximating Incremental Combinatorial Optimization Problems, Dynamic Matching Algorithms in Practice, A Weighted Linear Matroid Parity Algorithm, Efficient and Adaptive Parameterized Algorithms on Modular Decompositions, Finding nucleolus of flow game, Physical Computational Complexity and First-order Logic, A polynomial algorithm to find an independent set of maximum weight in a fork-free graph, Unnamed Item, The complexity of linear programming, A THEORY OF COMPLEXITY, CONDITION, AND ROUNDOFF, Induced Matchings in Graphs of Degree at Most 4, Independence and matching numbers of some token graphs, On Ramsey minimal graphs, Packing vertices and edges in random regular graphs, MAXIMUM WEIGHT CYCLE PACKING IN DIRECTED GRAPHS, WITH APPLICATION TO KIDNEY EXCHANGE PROGRAMS, Parameterized shifted combinatorial optimization, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Deterministic min-cost matching with delays, A polyhedral study of the maximum edge subgraph problem, On the anti-Kekulé problem of cubic graphs, Unnamed Item, Some bounds on the maximum induced matching numbers of certain grids, A survey on graphs with convex quadratic stability number, Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs, Connecting the dots (with minimum crossings), New Algorithms for Edge Induced König-Egerváry Subgraph Based on Gallai-Edmonds Decomposition, Impatient Online Matching, Distributed Approximate Maximum Matching in the CONGEST Model., Synteny Paths for Assembly Graphs Comparison, Planar Maximum Matching: Towards a Parallel Algorithm, Dispersing Obnoxious Facilities on a Graph, Complete Description of Matching Polytopes with One Linearized Quadratic Term for Bipartite Graphs, Spanning Trees with Few Branch Vertices, The k‐piece packing problem, Unnamed Item, Unnamed Item, Unnamed Item, A geometric theory for hypergraph matching, The maximum 1-2 matching problem and two kinds of its variants, Bipartite Perfect Matching is in Quasi-NC, Contracting a Planar Graph Efficiently, The Nonnegative Node Weight j-Restricted k-Matching Problems, Parameterized Algorithms and Kernels for Rainbow Matching, Unnamed Item, Logic and Complexity in Cognitive Science, Parameterized Graph Editing with Chosen Vertex Degrees, Parameterized Algorithms for Generalized Domination, Fully Dynamic Maximal Matching in $O(\log n)$ Update Time, An Introduction to Temporal Graphs: An Algorithmic Perspective*, Unnamed Item, Unnamed Item, Unnamed Item, Partial ML estimation for spatial autoregressive nonlinear probit models with autoregressive disturbances, On some parameters related to matching of graph powers, A Hybrid Approach to Fast Indirect Quadrilateral Mesh Generation
