Algorithmic complexity of finding cross-cycles in flag complexes

DOI10.1145/2261250.2261258MaRDI QIDQ2874564zbMATH OpenOpenAlexWikidataFDO

Authors Michał Adamaszek, Juraj Stacho

Publication date 7 August 2014

Published in Proceedings of the twenty-eighth annual symposium on Computational geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2261250.2261258

zbMATH Keywords

chordal graphscomputational topologyhomology groupsindependence complex

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Relations of low-dimensional topology with graph theory (57M15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• The complexity of detecting crossingfree configurations in the plane
• The complexity of computing the cylindrical and the \(t\)-circle crossing number of a graph
• Crossing Numbers and Parameterized Complexity
• On the complexity of crossings in permutations
• Computational complexity of covering cyclic graphs
• On the Complexity of Cycle Enumeration for Simple Graphs
• Complexity of cycle transverse matching problems
• Complexity of the circulant foliation over a graph

Cited in

(2)

• The Persistent Homology of Cyclic Graphs
• Complexity of simplicial homology and independence complexes of chordal graphs

This page was built for publication: Algorithmic complexity of finding cross-cycles in flag complexes

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