Complexity of simplicial homology and independence complexes of chordal graphs

DOI10.1016/J.COMGEO.2016.05.003MaRDI QIDQ679745zbMATHOpenAlexFDO

Authors Michał Adamaszek, Juraj Stacho

Publication date 19 January 2018

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.comgeo.2016.05.003

zbMATH Keywords

computational complexityhomologychordal graphclique complexindependence complex

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Recommendations

• Algorithmic complexity of finding cross-cycles in flag complexes
• Independence complexes of chordal graphs
• On the homology of independence complexes
• Higher chordality: from graphs to complexes
• A computationally intractable problem on simplicial complexes

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1254302 (Why is no real title available?)
• scientific article; zbMATH DE number 1961535 (Why is no real title available?)
• Algorithmic graph theory and perfect graphs
• Certain homology cycles of the independence complex of grids
• Combinatorial algebraic topology
• Complexes of directed trees and independence complexes
• Complexity and algorithms for Euler characteristic of simplicial complexes
• Computational aspects of monotone dualization: a brief survey
• Computational topology. An introduction
• Efficient edge domination in regular graphs
• Independence complexes of chordal graphs
• Induced matchings
• Note: Combinatorial Alexander duality -- a short and elementary proof
• On rigid circuit graphs
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• On the computational complexity of Betti numbers: reductions from matrix rank
• Perfect edge domination and efficient edge domination in graphs
• Recognition of collapsible complexes is NP-complete
• Shellable graphs and sequentially Cohen-Macaulay bipartite graphs
• Star clusters in independence complexes of graphs
• The topology of the independence complex
• Topology of random clique complexes
• Vertex decomposable graphs and obstructions to shellability
• Vietoris-Rips complexes of planar point sets

Cited in

(9)

• Strong Collapse for Persistence
• Strong collapse and persistent homology
• Graph pseudometrics from a topological point of view
• Computing persistent homology of flag complexes via strong collapses
• Perfect matching complexes of honeycomb graphs
• Non total-unimodularity neutralized simplicial complexes
• A note on independence complexes of chordal graphs and dismantling
• Sortable simplicial complexes and \(t\)-independence ideals of proper interval graphs
• Homotopy type of circle graph complexes motivated by extreme Khovanov homology

This page was built for publication: Complexity of simplicial homology and independence complexes of chordal graphs

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