Compressing Bounded Degree Graphs

DOI10.1007/978-3-662-49529-2_27MaRDI QIDQ2802953zbMATH OpenOpenAlexFDO

Authors Pål Grønås Drange, Markus Fanebust Dregi, R. B. Sandeep

Publication date 3 May 2016

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

Full work available at URL https://doi.org/10.1007/978-3-662-49529-2_27

Mathematics Subject Classification ID

Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Compressed Graphs and the Minimum Degree Algorithm
• Graph compression by BFS
• Compression of Graphical Structures: Fundamental Limits, Algorithms, and Experiments
• scientific article; zbMATH DE number 2170485
• Compression and Erdős-Ko-Rado graphs
• scientific article; zbMATH DE number 1555964
• Compact representation of graphs with bounded bandwidth or treedepth
• Simple efficient graph compression schemes for dense and complement graphs
• scientific article; zbMATH DE number 944226
• Efficient algorithms for decomposing graphs under degree constraints

Cited in

(3)

• On polynomial kernelization of \(\mathcal H\)-\textsc{free edge deletion}
• Cutting a tree with subgraph complementation is hard, except for some small trees
• Cutting a tree with subgraph complementation is hard, except for some small trees

This page was built for publication: Compressing Bounded Degree Graphs

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