Computing complexity measures of degenerate graphs

DOI10.4230/LIPICS.IPEC.2023.14MaRDI QIDQ6926196zbMATH OpenFDO

Authors Pål Grønås Drange, Patrick Greaves, Irene Muzi, Felix Reidl

Publication date 24 September 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.IPEC.2023.14

zbMATH Keywords

datastructuredegeneracyenumeratingVC-dimension

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parameterized complexity, tractability and kernelization (68Q27) Algorithms in computer science (68Wxx)

Cites work

• Arboricity and Subgraph Listing Algorithms
• Exact and approximate pattern counting in degenerate graphs: new algorithms, hardness results, and complexity dichotomies
• scientific article; zbMATH DE number 7650386 (Why is no real title available?)
• scientific article; zbMATH DE number 7829295 (Why is no real title available?)
• Listing all maximal cliques in large sparse real-world graphs
• Neighborhood complexity and kernelization for nowhere dense classes of graphs
• On limited nondeterminism and the complexity of the V-C dimension
• On the computational hardness based on linear fpt-reductions
• Progressive algorithms for domination and independence
• Set partitioning via inclusion-exclusion
• Smallest-last ordering and clustering and graph coloring algorithms
• Strong computational lower bounds via parameterized complexity
• Structural sparsity of complex networks: bounded expansion in random models and real-world graphs

Cited in

(1)

• Cycle counting under local differential privacy for degeneracy-bounded graphs

This page was built for publication: Computing complexity measures of degenerate graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6926196)