Efficient enumeration of maximal \(k\)-degenerate induced subgraphs of a chordal graph

DOI10.1016/j.tcs.2018.08.009zbMath1437.05102MaRDI QIDQ1985603

Yota Otachi, Takeaki Uno, Mamadou Moustapha Kanté, Kunihiro Wasa, Alessio Conte

Publication date: 7 April 2020

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2018.08.009

zbMATH Keywords

degeneracy; graph algorithms; chordal graphs; graph enumeration; clique trees; polynomial delay

Mathematics Subject Classification ID

05C05: Trees

05C30: Enumeration in graph theory

05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)

05C42: Density (toughness, etc.)