Algorithms on Subtree Filament Graphs

DOI10.1007/978-3-642-02029-2_3zbMath1194.05144OpenAlexW1520704862MaRDI QIDQ3655136

Fanica Gavril

Publication date: 7 January 2010

Published in: Graph Theory, Computational Intelligence and Thought (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-02029-2_3

zbMATH Keywords

perfect graphsubtree filament graphdominating holeinduced split subgraph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (5)

Approximation algorithms for maximum weight k-coverings of graphs by packings ⋮ Algorithms for \(\mathcal{GA}\mathrm{-}\mathcal H\) reduced graphs ⋮ Maximum max-k-clique subgraphs in cactus subtree graphs ⋮ Algorithms for induced biclique optimization problems ⋮ Maximum weight induced multicliques and complete multipartite subgraphs in directed path overlap graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maximum weight independent sets and cliques in intersection graphs of filaments
• The strong perfect graph theorem
• Comparability graphs and intersection graphs
• Induced matchings in intersection graphs.
• Subtree filament graphs are subtree overlap graphs
• Note on maximal split-stable subgraphs
• 3D-interval-filament graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Domination on Cocomparability Graphs
• Recognition of Polygon-Circle Graphs and Graphs of Interval Filaments Is NP-Complete
• Algorithms on circular-arc graphs

This page was built for publication: Algorithms on Subtree Filament Graphs