Counting hexagonal patches and independent sets in circle graphs
From MaRDI portal
Publication:2429365
DOI10.1007/s00453-011-9561-yzbMath1239.05093OpenAlexW2064729717MaRDI QIDQ2429365
Publication date: 26 April 2012
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-011-9561-y
Applications of graph theory (05C90) Enumeration in graph theory (05C30) Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (2)
A Faster Algorithm for Maximum Induced Matchings on Circle Graphs ⋮ A Maximum Weight Clique Algorithm For Dense Circle Graphs With Many Shared Endpoints
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Filling of a given boundary by \(p\)-gons and related problems
- Numbers of faces in disordered patches
- Reducing prime graphs and recognizing circle graphs
- Detecting and decomposing self-overlapping curves
- The nature and meaning of perturbations in geometric computing
- Pentagon-hexagon-patches with short boundaries
- Boundary uniqueness of fusenes
- Finding Fullerene Patches in Polynomial Time
- Graph Classes: A Survey
- Recognition of Circle Graphs
- Recognizing circle graphs in polynomial time
- Algorithms and Computation
- Efficiently implementing maximum independent set algorithms on circle graphs
- Algorithms for a maximum clique and a maximum independent set of a circle graph
- A constructive enumeration of nanotube caps
- Extensions to the disk of properly nested plane immersions of the circle
This page was built for publication: Counting hexagonal patches and independent sets in circle graphs