scientific article; zbMATH DE number 7375982

DOI10.4230/LIPIcs.ICALP.2018.55zbMath1503.91076MaRDI QIDQ5002730

Tim Roughgarden, C. Seshadhri, Fan Wei, Jacob Fox, Nicole Wein

Publication date: 28 July 2021

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

social networksgraph algorithmsfixed-parameter tractability

Mathematics Subject Classification ID

Social networks; opinion dynamics (91D30) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (3)

Map graphs having witnesses of large girth ⋮ Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems ⋮ A trust model for spreading gossip in social networks: a multi-type bootstrap percolation model

Uses Software

• KronFit

Cites Work

• Unnamed Item
• Unnamed Item
• The clique density theorem
• Hypergraph containers
• On graphs without a \(C_{4}\) or a diamond
• On the maximum number of cliques in a graph embedded in a surface
• The worst-case time complexity for generating all maximal cliques and computational experiments
• An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments
• Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
• Faster multi-witnesses for Boolean matrix multiplication
• Connected components in random graphs with given expected degree sequences
• On the number of cliques in graphs with a forbidden minor
• On the hardness of optimization in power-law graphs
• From the Cover: The structure of scientific collaboration networks
• Decompositions of Triangle-Dense Graphs
• Detecting high log-densities
• Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time
• The number of cliques in graphs of given order and size
• Emergence of Scaling in Random Networks
• Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters
• The small-world phenomenon
• On the Minimal Density of Triangles in Graphs
• On the Hardness of Optimization in Power Law Graphs
• A New Algorithm for Generating All the Maximal Independent Sets
• Community structure in social and biological networks
• Algorithmic Complexity of Power Law Networks
• Independent sets in hypergraphs
• Collective dynamics of ‘small-world’ networks
• The average distances in random graphs with given expected degrees
• Parameterized Algorithms
• On cliques in graphs

This page was built for publication: