Complexity of simplicial homology and independence complexes of chordal graphs

DOI10.1016/J.COMGEO.2016.05.003zbMATH Open1386.65086OpenAlexW2370347111MaRDI QIDQ679745FDOQ679745

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

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

zbMATH Keywords

computational complexityhomologychordal graphclique complexindependence complex

Mathematics Subject Classification ID

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

Cites Work

• Topology of random clique complexes
• Computational topology. An introduction
• Title not available (Why is that?)
• Algorithmic graph theory and perfect graphs
• On rigid circuit graphs
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• Shellable graphs and sequentially Cohen-Macaulay bipartite graphs
• Complexes of directed trees and independence complexes
• Induced matchings
• Vertex decomposable graphs and obstructions to shellability
• Efficient edge domination in regular graphs
• Perfect edge domination and efficient edge domination in graphs
• Title not available (Why is that?)
• Computational aspects of monotone dualization: a brief survey
• Star clusters in independence complexes of graphs
• Combinatorial algebraic topology
• The topology of the independence complex
• Certain homology cycles of the independence complex of grids
• Note: Combinatorial Alexander duality -- a short and elementary proof
• Independence complexes of chordal graphs
• Title not available (Why is that?)
• Vietoris-Rips complexes of planar point sets
• Recognition of collapsible complexes is NP-complete
• Complexity and algorithms for Euler characteristic of simplicial complexes
• On the Computational Complexity of Betti Numbers: Reductions from Matrix Rank

Cited In (8)

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

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)