Computing the degeneracy of large graphs

DOI10.1007/978-3-642-54423-1_22MaRDI QIDQ5405044zbMATH OpenOpenAlexFDO

Authors Martin Farach-Colton, Meng-Tsung Tsai

Publication date 31 March 2014

Published in LATIN 2014: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-54423-1_22

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• Tight Approximations of Degeneracy in Large Graphs
• External-memory network analysis algorithms for naturally sparse graphs
• Automata, Languages and Programming
• Listing all maximal cliques in large sparse real-world graphs
• On graph problems in a semi-streaming model

Cited in

(11)

• Degeneracy graphs and the neighbourhood problem
• Degeneracy subgraph of the Lemke complementary pivot algorithm and anticycling rule
• Single-pass streaming algorithms to partition graphs into few forests
• Tight Approximations of Degeneracy in Large Graphs
• External-memory network analysis algorithms for naturally sparse graphs
• scientific article; zbMATH DE number 5994667 (Why is no real title available?)
• Finding articulation points of large graphs in linear time
• Decomposing large graphs with small graphs of high density
• Computing the largest bond of a graph
• Polynomial pass semi-streaming lower bounds for k-cores and degeneracy
• On the generalized mean densest subgraph problem: complexity and algorithms

This page was built for publication: Computing the degeneracy of large graphs

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