Maximum weight independent sets and cliques in intersection graphs of filaments

DOI10.1016/S0020-0190(00)00025-9zbMath1339.05287OpenAlexW2078024271MaRDI QIDQ294733

Fanica Gavril

Publication date: 16 June 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: http://www.sciencedirect.com/science/article/pii/S0020019000000259?np=y

zbMATH Keywords

graphintersection graphgraph algorithmsinterval graphmaximum independent setmaximum cliquechordalcircular-arc graphpolygon-circle graph

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (41)

MINIMUM WEIGHT FEEDBACK VERTEX SETS IN CIRCLE n-GON GRAPHS AND CIRCLE TRAPEZOID GRAPHS ⋮ On the structure of certain intersection graphs ⋮ Subtree filament graphs are subtree overlap graphs ⋮ Induced Separation Dimension ⋮ Graphs of edge-intersecting non-splitting paths in a tree: representations of holes. I ⋮ Approximation algorithms for maximum weight k-coverings of graphs by packings ⋮ Cops and robbers on intersection graphs ⋮ Fixed interval scheduling: models, applications, computational complexity and algorithms ⋮ Convex Recoloring Revisited: Complexity and Exact Algorithms ⋮ New insights on \(\mathbf{GA}\)-\(\mathbf H\) reduced graphs ⋮ On Strict (Outer-)Confluent Graphs ⋮ A faster algorithm for maximum independent set on interval filament graphs ⋮ A Faster Algorithm for Maximum Induced Matchings on Circle Graphs ⋮ Algorithms for \(\mathcal{GA}\mathrm{-}\mathcal H\) reduced graphs ⋮ Maximum max-k-clique subgraphs in cactus subtree graphs ⋮ Recognition of Polygon-Circle Graphs and Graphs of Interval Filaments Is NP-Complete ⋮ Grounded \(\mathrm{L}\)-graphs are polynomially \(\chi \)-bounded ⋮ Algorithms for induced biclique optimization problems ⋮ Maximum independent set and maximum clique algorithms for overlap graphs ⋮ On strict (outer-)confluent graphs ⋮ Robust maximum weighted independent-set problems on interval graphs ⋮ Induced matchings in intersection graphs. ⋮ 3D-interval-filament graphs ⋮ An algorithm for the maximum weight independent set problem on outerstring graphs ⋮ The critical node detection problem in networks: a survey ⋮ Minimum weight feedback vertex sets in circle graphs ⋮ Towards a comprehensive theory of conflict-tolerance graphs ⋮ The complexity of dissociation set problems in graphs ⋮ Maximum weight induced multicliques and complete multipartite subgraphs in directed path overlap graphs ⋮ On-line approach to off-line coloring problems on graphs with geometric representations ⋮ The induced separation dimension of a graph ⋮ Approximating the minimum clique cover and other hard problems in subtree filament graphs ⋮ Finding a maximum induced matching in weakly chordal graphs ⋮ Maximum Independent Set in 2-Direction Outersegment Graphs ⋮ Algorithms on Subtree Filament Graphs ⋮ The graphs with maximum induced matching and maximum matching the same size ⋮ Distributed interactive proofs for the recognition of some geometric intersection graph classes ⋮ Independent packings in structured graphs ⋮ Algorithms for maximum weight induced paths ⋮ The maximum clique problem in multiple interval graphs ⋮ The \(k\)-separator problem: polyhedra, complexity and approximation results

Cites Work

• Unnamed Item
• Unnamed Item
• Trapezoid graphs and generalizations, geometry and algorithms
• Decomposition by clique separators
• Comparability graphs and intersection graphs
• Thresholds for classes of intersection graphs
• Intersection graphs of Helly families of subtrees
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Algorithms on circular-arc graphs
• Recognition of Circle Graphs
• $O(M\cdot N)$ Algorithms for the Recognition and Isomorphism Problems on Circular-Arc Graphs
• Algorithms for a maximum clique and a maximum independent set of a circle graph

This page was built for publication: Maximum weight independent sets and cliques in intersection graphs of filaments