TWO THEOREMS IN GRAPH THEORY
From MaRDI portal
Publication:3258697
DOI10.1073/pnas.43.9.842zbMath0086.16202OpenAlexW2048652909WikidataQ37690025 ScholiaQ37690025MaRDI QIDQ3258697
Publication date: 1957
Published in: Proceedings of the National Academy of Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1073/pnas.43.9.842
Related Items
Tight bounds on maximal and maximum matchings, A greedy and distributable approach to the Lexicographic Bottleneck Assignment Problem with conditions on exactness, An \(\mathcal{O}(m\log n)\) algorithm for the weighted stable set problem in claw-free graphs with \(\alpha ({G}) \leq 3\), Augmenting approach for some maximum set problems, An \(O(n)\) time algorithm for maximum matching in \(P_{4}\)-tidy graphs, Hierarchical \(b\)-matching, On the ratio between maximum weight perfect matchings and maximum weight matchings in grids, A polynomial time solvable instance of the feasible minimum cover problem, A \((3+\epsilon)k\)-vertex kernel for edge-disjoint triangle packing, Tutte sets in graphs. II: The complexity of finding maximum Tutte sets, Finding maximum matching for bipartite graphs in parallel, Gallai-Edmonds decomposition as a pruning technique, Combinatorics and algorithms for augmenting graphs, Nonconvergence, undecidability, and intractability in asymptotic problems, An approximation algorithm for the load-balanced semi-matching problem in weighted bipartite graphs, Circular convex bipartite graphs: Maximum matching and Hamiltonian circuits, Some results on Berge's conjecture and begin-end conjecture, Structural identifiability in low-rank matrix factorization, On some algorithmic investigations of star partitions of graphs, Dynamic matchings in left vertex weighted convex bipartite graphs, Finding a maximum matching in a permutation graph, The general maximum matching algorithm of Micali and Vazirani, Supereulerian graphs with constraints on the matching number and minimum degree, Erdős-Ko-Rado for perfect matchings, From matchings to independent sets, Independence and matching numbers of unicyclic graphs from null space, Allocating costs in set covering problems, Converting triangulations to quadrangulations, Maximum \((s,t)\)-flows in planar networks in \(\mathcal O(|V| \log |V|)\) time, Recovery of disrupted airline operations using \(k\)-maximum matching in graphs, A generalized Hungarian method for solving minimum weight perfect matching problems with algebraic objective, A \(0(| V | \cdot | E |)\) algorithm for maximum matching of graphs, On maximal independent sets of vertices in claw-free graphs, Bottleneck partial-matching Voronoi diagrams and applications, On generalized matching problems, Bipartite matching in the semi-streaming model, Weighted inverse maximum perfect matching problems under the Hamming distance, Variations on a theorem of Petersen, An efficient distributed algorithm for maximum matching in general graphs, Fair-by-design matching, Forbidden subgraphs and the König-Egerváry property, Perfect matchings as IID factors on non-amenable groups, On matching cover of graphs, Triangle strings: structures for augmentation of vertex-disjoint triangle sets, A reduction algorithm for the weighted stable set problem in claw-free graphs, Implicit computation of maximum bipartite matchings by sublinear functional operations, Maximum \((g,f)\)-factors of a general graph, On \((k+1)\)-line graphs of \(k\)-trees and their nullities, Dulmage-Mendelsohn canonical decomposition as a generic pruning technique, An introduction to randomized algorithms, Matching and spanning trails in digraphs, The \(b\)-\textsc{Matching} problem in distance-hereditary graphs and beyond, The extremal values of some topological indices in bipartite graphs with a given matching number, Nash equilibria in the two-player kidney exchange game, On paths avoding forbidden pairs of vertices in a graph, A \(\{-1,0,1\}\)- and sparsest basis for the null space of a forest in optimal time, On complexity of special maximum matchings constructing, Maximum fractional factors in graphs, On two extensions of equimatchable graphs, Composability and controllability of structural linear time-invariant systems: distributed verification, On finding augmenting graphs, Julius Petersen's theory of regular graphs, Matching theory -- a sampler: From Dénes König to the present, Finding a maximum matching in a circular-arc graph, Complete subgraphs of the coprime hypergraph of integers. III: Construction, Matchings in graphs. II, Augmenting graphs for independent sets, Augmenting chains in graphs without a skew star., Maximum independent sets in subclasses of \(P_{5}\)-free graphs, Covers, matchings and odd cycles of a graph, Toughness in graphs -- a survey, Finding maximum square-free 2-matchings in bipartite graphs, Linear algorithms for testing the sign stability of a matrix and for finding Z-maximum matchings in acyclic graphs, Berge's theorem for the maximum charge problem, Condensed Ricci curvature of complete and strongly regular graphs, Coalitional games induced by matching problems: complexity and islands of tractability for the Shapley value, Sparse regular induced subgraphs in \(2P_3\)-free graphs, Stabilizing network bargaining games by blocking players, On improving matchings in trees, via bounded-length augmentations, Cardinality of relations with applications, Finding augmenting chains in extensions of claw-free graphs, The combinatorics of N. G. de Bruijn, Stabilizing maximum matching in bipartite networks, Combinatorial characterizations of the saturation and the associated primes of the fourth power of edge ideals, \(b\)-coloring is NP-hard on co-bipartite graphs and polytime solvable on tree-cographs, Heuristically guided search and chromosome matching, M-alternating Hamilton paths and \(M\)-alternating Hamilton cycles, ``Global graph problems tend to be intractable, Using clausal graphs to determine the computational complexity of \(k\)-bounded positive one-in-three SAT, Path problems in skew-symmetric graphs, Linear-time certifying algorithms for near-graphical sequences, A characterization of König-Egerváry graphs with extendable vertex covers, The graphs with maximum induced matching and maximum matching the same size, Recomputing causality assignments on lumped process models when adding new simplification assumptions, An extension of matching theory, Polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference., On an interpolation property of outerplanar graphs, Priority matchings revisited, A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm, A condition on Hamilton-connected line graphs, Maximum and optimal 1-2 matching problem of the different kind, Implicit Computation of Maximum Bipartite Matchings by Sublinear Functional Operations, Generalized XOR non-locality games with graph description on a square lattice, Stabilizing Network Bargaining Games by Blocking Players, Using Relations to Develop a Haskell Program for Computing Maximum Bipartite Matchings, Packings by Complete Bipartite Graphs, A UNIFIED APPROACH TO AUTOMATIC LABEL PLACEMENT, PARALLEL APPROXIMATE MATCHING, The use of a pruned modular decomposition for \textsc{maximum matching} algorithms on some graph classes, Benders decomposition for network design covering problems, Tiling with Squares and Packing Dominos in Polynomial Time, A New Algorithm for the Maximum Weighted Stable Set Problem in Claw-Free Graphs, Identifying optimal strategies in kidney exchange games is \(\varSigma_2^p\)-complete, Unnamed Item, New approximation results on graph matching and related problems, Linear Time Approximation Algorithms for Degree Constrained Subgraph Problems, Augmenting trail theorem for the maximum 1-2 matching problem, On maximum matchings in cubic graphs with a bounded number of bridge-covering paths, Covers and packings in a family of sets, An efficient algorithm for minimumk-covers in weighted graphs, Dynamic Matching Algorithms in Practice, Parameterized Algorithms for the Independent Set Problem in Some Hereditary Graph Classes, State-of-the-Art Sparse Direct Solvers, Unnamed Item, A polynomial algorithm to find an independent set of maximum weight in a fork-free graph, Unnamed Item, A survey of direct methods for sparse linear systems, Unnamed Item, Unnamed Item, Unnamed Item, Combinatorial Aspects in Sparse Elimination Methods, Recovery of disrupted airline operations using \(k\)-maximum matching in graphs, Expected time complexity of the auction algorithm and the push relabel algorithm for maximum bipartite matching on random graphs, Supereulerian Digraphs with Large Arc-Strong Connectivity, Cayley factorization and the area principle, Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs, The maximum 1-2 matching problem and two kinds of its variants, The support unit location problem to road traffic surveys with multi-stages, An Algorithm for a Minimum Cover of a Graph, BIPARTITE GRAPHS TOTALLY DECOMPOSABLE BY CANONICAL DECOMPOSITION
