Maximum weight independent sets and cliques in intersection graphs of filaments
DOI10.1016/S0020-0190(00)00025-9zbMATH Open1339.05287OpenAlexW2078024271MaRDI QIDQ294733FDOQ294733
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
Recommendations
graphmaximum cliquegraph algorithmsintersection graphinterval graphmaximum independent setchordalcircular-arc graphpolygon-circle graph
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)
Cites Work
- Decomposition by clique separators
- Comparability graphs and intersection graphs
- Algorithms on circular-arc graphs
- $O(M\cdot N)$ Algorithms for the Recognition and Isomorphism Problems on Circular-Arc Graphs
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Thresholds for classes of intersection graphs
- Intersection graphs of Helly families of subtrees
- Recognition of Circle Graphs
- Algorithms for a maximum clique and a maximum independent set of a circle graph
- Trapezoid graphs and generalizations, geometry and algorithms
Cited In (43)
- A faster algorithm for maximum independent set on interval filament graphs
- The graphs with maximum induced matching and maximum matching the same size
- Minimum weight feedback vertex sets in circle \(n\)-gon graphs and circle trapezoid graphs
- Convex Recoloring Revisited: Complexity and Exact Algorithms
- Towards a comprehensive theory of conflict-tolerance graphs
- Algorithms on Subtree Filament Graphs
- Minimum weight feedback vertex sets in circle graphs
- Approximating the minimum clique cover and other hard problems in subtree filament graphs
- Independent packings in structured graphs
- On strict (outer-)confluent graphs
- On strict (outer-)confluent graphs
- A Faster Algorithm for Maximum Induced Matchings on Circle Graphs
- On the structure of certain intersection graphs
- Maximum independent set in 2-direction outersegment graphs
- Grounded \(\mathrm{L}\)-graphs are polynomially \(\chi \)-bounded
- The complexity of dissociation set problems in graphs
- Approximation algorithms for maximum weight k-coverings of graphs by packings
- On-line approach to off-line coloring problems on graphs with geometric representations
- The induced separation dimension of a graph
- Traversing combinatorial 0/1-polytopes via optimization
- Maximum independent set and maximum clique algorithms for overlap graphs
- Maximum weight induced multicliques and complete multipartite subgraphs in directed path overlap graphs
- Maximum max-k-clique subgraphs in cactus subtree graphs
- Robust maximum weighted independent-set problems on interval graphs
- Recognising the overlap graphs of subtrees of restricted trees is hard
- Graphs of edge-intersecting non-splitting paths in a tree: representations of holes. I
- Algorithms for \(\mathcal{GA}\mathrm{-}\mathcal H\) reduced graphs
- Cops and robbers on intersection graphs
- Algorithms for maximum weight induced paths
- Fixed interval scheduling: models, applications, computational complexity and algorithms
- Subtree filament graphs are subtree overlap graphs
- The maximum clique problem in multiple interval graphs
- New insights on \(\mathbf{GA}\)-\(\mathbf H\) reduced graphs
- Algorithms for induced biclique optimization problems
- Induced separation dimension
- The critical node detection problem in networks: a survey
- Induced matchings in intersection graphs.
- Recognition of Polygon-Circle Graphs and Graphs of Interval Filaments Is NP-Complete
- 3D-interval-filament graphs
- The \(k\)-separator problem: polyhedra, complexity and approximation results
- Finding a maximum induced matching in weakly chordal graphs
- Distributed interactive proofs for the recognition of some geometric intersection graph classes
- An algorithm for the maximum weight independent set problem on outerstring 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)
