On the complexity of the independent set problem in triangle graphs
From MaRDI portal
Publication:2275391
Recommendations
- The complexity of some problems on maximal independent sets in graphs
- On the complexity of approximating the independent set problem
- Structural Information and Communication Complexity
- Finding Independent Sets in Triangle-Free Graphs
- Minimizing the number of independent sets in triangle-free regular graphs
- scientific article; zbMATH DE number 1107725
- On the complexity of approximating the independent set problem (extended abstract)
- On approximation properties of the Independent set problem for degree 3 graphs
- Analysis of the influence of the number of edges on the complexity of the independent set problem
- Polynomial-time solvability of the independent set problem in a certain class of subcubic planar graphs
Cites work
- scientific article; zbMATH DE number 3882430 (Why is no real title available?)
- scientific article; zbMATH DE number 3882470 (Why is no real title available?)
- scientific article; zbMATH DE number 3926973 (Why is no real title available?)
- scientific article; zbMATH DE number 1330033 (Why is no real title available?)
- scientific article; zbMATH DE number 1095171 (Why is no real title available?)
- scientific article; zbMATH DE number 1182757 (Why is no real title available?)
- scientific article; zbMATH DE number 3445275 (Why is no real title available?)
- scientific article; zbMATH DE number 2190095 (Why is no real title available?)
- scientific article; zbMATH DE number 969982 (Why is no real title available?)
- A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
- A characterization and hereditary properties for partition graphs
- A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
- Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
- An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph
- Bipartite bihypergraphs: a survey and new results
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Complement reducible graphs
- Computing independent sets in graphs with large girth
- Graph Classes: A Survey
- Graph theory
- Graph-Theoretic Concepts in Computer Science
- Greed is good: Approximating independent sets in sparse and bounded-degree graphs
- Independent Sets in Asteroidal Triple-Free Graphs
- Independent dominating and neighborhood sets in triangular graphs
- Independent sets in extensions of 2\(K_{2}\)-free graphs
- Independent sets of maximum weight in apple-free graphs
- Linear degree extractors and the inapproximability of max clique and chromatic number
- Maximum independent sets in subclasses of \(P_{5}\)-free graphs
- Maximum weighted independent sets on transitive graphs and applications
- On graphs whose maximal cliques and stable sets intersect
- On graphs with polynomially solvable maximum-weight clique problem
- On maximal independent sets of vertices in claw-free graphs
- On split and almost CIS-graphs
- On the approximability of an interval scheduling problem
- Polar graphs and maximal independent sets
- Polynomial algorithm for finding the largest independent sets in graphs without forks
- Polynomially solvable cases for the maximum stable set problem
- Scheduling jobs within time windows on identical parallel machines: New model and algorithms
- Some covering concepts in graphs
- Some parameters on neighborhood number of A graph
- Some results on graphs without long induced paths
- Stability in CAN-free graphs
- The independent neighbourhood number of a graph
- The maximum independent set problem for cubic planar graphs
- Two-Processor Scheduling with Start-Times and Deadlines
Cited in
(14)- Short proofs on the structure of general partition, equistable and triangle graphs
- Strong cliques and equistability of EPT graphs
- On equistable, split, CIS, and related classes of graphs
- Complexity results for triangular sets
- scientific article; zbMATH DE number 7650229 (Why is no real title available?)
- Triangle width problem: at the intersection of graph theory, scheduling, and matrix visualization
- Domination triangle graphs and upper bound graphs
- Algorithm to find a maximum 2-packing set in a cactus
- scientific article; zbMATH DE number 7742928 (Why is no real title available?)
- Independent Domination in Triangle Graphs
- 1-Triangle graphs and perfect neighborhood sets
- The impact of the growth rate of the packing number of graphs on the computational complexity of the independent set problem
- Equistable simplicial, very well-covered, and line graphs
- Characterization of general position sets and its applications to cographs and bipartite graphs
This page was built for publication: On the complexity of the independent set problem in triangle graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2275391)
