TWO THEOREMS IN GRAPH THEORY
From MaRDI portal
Publication:3258697
DOI10.1073/PNAS.43.9.842zbMath0086.16202OpenAlexW2048652909WikidataQ37690025 ScholiaQ37690025MaRDI QIDQ3258697
No author found.
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 (only showing first 100 items - show all)
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
This page was built for publication: TWO THEOREMS IN GRAPH THEORY
