An algorithm for the maximum weight independent set problem on outerstring graphs
DOI10.1016/J.COMGEO.2016.05.001zbMATH Open1378.05154OpenAlexW2382079786MaRDI QIDQ680149FDOQ680149
Authors: J. Mark Keil, Joseph S. B. Mitchell, D. Pradhan, Martin Vatshelle 
Publication date: 22 January 2018
Published in: Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.comgeo.2016.05.001
Recommendations
- Computing maximum independent set on outerstring graphs and their relatives
- Computing maximum independent set on outerstring graphs and their relatives
- Algorithms and Computation
- Exact algorithms for maximum weighted independent set on sparse graphs (extended abstract)
- An efficient algorithm for finding a maximum weight 2-independent set on interval graphs
- A note on greedy algorithms for the maximum weighted independent set problem
- scientific article; zbMATH DE number 2119675
- An optimal maximal independent set algorithm for bounded-independence graphs
- The weighted maximum independent set problem in permutation graphs
Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Cites Work
- Comparability graphs and intersection graphs
- The max clique problem in classes of string-graphs
- The clique problem in ray intersection graphs
- Every planar graph is the intersection graph of segments in the plane (extended abstract)
- Vertex disjoint paths for dispatching in railways
- Maximum weight independent sets and cliques in intersection graphs of filaments
- Data Mining with optimized two-dimensional association rules
- Intersection graphs of curves in the plane
- Title not available (Why is that?)
- Computing the independence number of intersection graphs
- Recognizing string graphs in NP
- Label placement by maximum independent set in rectangles
- Coloring \(K_{k}\)-free intersection graphs of geometric objects in the plane
- String graphs and incomparability graphs
- Topology of Thin Film RC Circuits
- String graphs. II: Recognizing string graphs is NP-hard
- String graphs requiring exponential representations
- Noncrossing Subgraphs in Topological Layouts
- String graphs. I: The number of critical nonstring graphs is infinite
- On the rectangle escape problem
- Maximum independent set in 2-direction outersegment graphs
- Title not available (Why is that?)
Cited In (21)
- An optimal time algorithm for finding a maximum weight independent set in a tree
- Generalized disk graphs
- Order-preserving 1-string representations of planar graphs
- Packing boundary-anchored rectangles and squares
- A Faster Algorithm for Maximum Induced Matchings on Circle Graphs
- Maximum independent set in 2-direction outersegment graphs
- Faster multi-sided one-bend boundary labelling
- Algorithm to find a maximum 2-packing set in a cactus
- On dominating set of some subclasses of string graphs
- Finding a Maximum Clique in a Grounded 1-Bend String Graph
- An algorithm for finding a maximum weighted independent set in an arbitrary graph
- Approximating dominating set on intersection graphs of rectangles and \(\mathsf{L}\)-frames
- An algorithm for outerplanar graphs with parameter
- On the size of outer-string representations
- Boundary labeling for rectangular diagrams
- Intersection graphs of rays and grounded segments
- On approximating MIS over B1-VPG graphs*
- Approximating dominating set on intersection graphs of rectangles and L-frames
- The Maximum Disjoint Routing Problem
- Polygon simplification by minimizing convex corners
- Computing maximum independent set on outerstring graphs and their relatives
This page was built for publication: An algorithm for the maximum weight independent set problem on outerstring graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q680149)
