Finding a Maximum Clique in a Grounded 1-Bend String Graph

DOI10.7155/JGAA.00608MaRDI QIDQ5886042zbMATH OpenOpenAlexFDO

Authors J. Mark Keil, Debajyoti Mondal, E. Moradi, Yakov Nekrich

Publication date 30 March 2023

Published in Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2107.05198

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• The density of complex zeros of random sums
• On roots of random polynomials
• Complex roots of a class of random algebraic polynomials
• Real zeros of random sums with i.i.d. coefficients
• Complex roots of a random algebraic polynomial

Cites work

• An algorithm for the maximum weight independent set problem on outerstring graphs
• An output sensitive algorithm for computing a maximum independent set of a circle graph
• Computing maximum independent set on outerstring graphs and their relatives
• Computing the independence number of intersection graphs
• Fast distance multiplication of unit-Monge matrices
• Four-dimensional dominance range reporting in linear space
• scientific article; zbMATH DE number 4200260 (Why is no real title available?)
• scientific article; zbMATH DE number 1433426 (Why is no real title available?)
• Intersection graphs of rays and grounded segments
• Minimum shared‐power edge cut
• On grounded -graphs and their relatives
• Orthogonal range searching on the RAM, revisited
• Sequential and parallel algorithms for the maximum-weight independent set problem on permutation graphs
• The Complexity of Combinatorial Optimization Problems on d‐Dimensional Boxes
• The max clique problem in classes of string-graphs
• Topics in Intersection Graph Theory
• Topology of Thin Film RC Circuits

Cited in

(2)

• The density of complex zeros of random sums
• The maximum clique problem in a disk graph made easy

This page was built for publication: Finding a Maximum Clique in a Grounded 1-Bend String Graph

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