Maximum matchings in scale-free networks with identical degree distribution

DOI10.1016/j.tcs.2017.02.027zbMath1370.68233arXiv1703.09041OpenAlexW2592053950MaRDI QIDQ528496

Zhong-Zhi Zhang, Hu-An Li

Publication date: 12 May 2017

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1703.09041

zbMATH Keywords

maximum matchingPfaffian orientationperfect matchingcomplex networkscale-free network

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items

MAXIMUM MATCHINGS IN A PSEUDOFRACTAL SCALE-FREE WEB ⋮ Maximum matchings and minimum dominating sets in Apollonian networks and extended tower of Hanoi graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maximum matching in multi-interface networks
• Counting dimer coverings on self-similar Schreier graphs
• Applications of graphical condensation for enumerating matchings and tilings
• The complexity of computing the permanent
• Farey graphs as models for complex networks
• Local characteristics, entropy and limit theorems for spanning trees and domino tilings via transfer-impedances
• Graphical condensation of plane graphs: a combinatorial approach
• The number and degree distribution of spanning trees in the Tower of Hanoi graph
• Pfaffian orientation and enumeration of perfect matchings for some Cartesian products of graphs
• Exact and asymptotic enumeration of perfect matchings in self-similar graphs
• Matching theory
• On the theory of Pfaffian orientations. I: Perfect matchings and permanents
• Generalized domino-shuffling.
• Number of maximum matchings of bipartite graphs with positive surplus
• Graphical condensation for enumerating perfect matchings
• On the number of perfect matchings of line graphs
• Maximum matching in regular and almost regular graphs
• Structural properties of subdivided-line graphs
• A quadratic identity for the number of perfect matchings of plane graphs
• Dimers and amoebae
• Enumeration of perfect matchings of a type of Cartesian products of graphs
• Unique Maximum Matching Algorithms
• The statistics of dimers on a lattice
• Inverted Berezinskii-Kosterlitz-Thouless singularity and high-temperature algebraic order in an Ising model on a scale-free hierarchical-lattice small-world network
• The Tower of Hanoi – Myths and Maths
• Applications of Perfect Matchings in Chemistry
• Emergence of Scaling in Random Networks
• Controllability and matchings in random bipartite graphs
• A new NC-algorithm for finding a perfect matching in bipartite planar and small genus graphs (extended abstract)
• DIMERS ON TWO-DIMENSIONAL LATTICES
• Finding a maximum matching in a sparse random graph in O ( n ) expected time
• A box-covering algorithm for fractal scaling in scale-free networks
• The Complexity of Enumeration and Reliability Problems
• The Structure and Function of Complex Networks
• The number of matchings in random graphs
• Dimer problem in statistical mechanics-an exact result
• Collective dynamics of ‘small-world’ networks
• Crossing numbers of Sierpiński‐like graphs

This page was built for publication: Maximum matchings in scale-free networks with identical degree distribution