Maximum weight independent sets and cliques in intersection graphs of filaments

DOI10.1016/S0020-0190(00)00025-9MaRDI QIDQ294733zbMATH OpenOpenAlexFDO

Authors 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

graphmaximum cliquegraph algorithmsintersection graphinterval graphmaximum independent setchordalcircular-arc graphpolygon-circle graph

Mathematics Subject Classification ID

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) Structural characterization of families of graphs (05C75)

Recommendations

• 3D-interval-filament graphs
• On the structure of certain intersection graphs
• A faster algorithm for maximum independent set on interval filament graphs
• New clique and independent set algorithms for circle graphs
• Algorithms and Computation

Cites work

• scientific article; zbMATH DE number 3566474 (Why is no real title available?)
• scientific article; zbMATH DE number 3225808 (Why is no real title available?)
• $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
• Algorithms on circular-arc graphs
• Comparability graphs and intersection graphs
• Decomposition by clique separators
• Intersection graphs of Helly families of subtrees
• Recognition of Circle Graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Thresholds for classes of intersection graphs
• Trapezoid graphs and generalizations, geometry and algorithms

Cited in

(42)

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

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

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