Pages that link to "Item:Q1230637"
From MaRDI portal
The following pages link to Some simplified NP-complete graph problems (Q1230637):
Displayed 50 items.
- Partitioning graphs into complete and empty graphs (Q1045126) (← links)
- Planar graphs without adjacent cycles of length at most seven are 3-colorable (Q1045158) (← links)
- Efficient bounds for the stable set, vertex cover and set packing problems (Q1056763) (← links)
- Complete problems for space bounded subclasses of NP (Q1064779) (← links)
- A polynomial time heuristic for certain subgraph optimization problems with guaranteed worst case bound (Q1071037) (← links)
- Quadratic functions with exponential number of local maxima (Q1079496) (← links)
- Performance ratio of polynomial heuristics for triangle inequality quadratic assignment problems (Q1080776) (← links)
- Implications of forbidden structures for extremal algorithmic problems (Q1082812) (← links)
- Graph theoretic closure properties of the family of boundary NLC graph languages (Q1084870) (← links)
- On gallery watchmen in grids (Q1087018) (← links)
- On the complexity of the maximum satisfiability problem for Horn formulas (Q1099168) (← links)
- A parallel algorithm for bisection width in trees (Q1103410) (← links)
- Probabilistic satisfiability (Q1104751) (← links)
- The complexity of optimization problems (Q1107309) (← links)
- More complicated questions about maxima and minima, and some closures of NP (Q1107524) (← links)
- A polynomial characterization of some graph partitioning problems (Q1108810) (← links)
- The complexity of multicolouring (Q1113919) (← links)
- Optimal product design using conjoint analysis: Computational complexity and algorithms (Q1115344) (← links)
- A randomised 3-colouring algorithm (Q1117242) (← links)
- A hierarchy of propositional Horn formuls (Q1122571) (← links)
- The complexity of matching with bonds (Q1123620) (← links)
- On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three (Q1123898) (← links)
- An NC algorithm for Brooks' theorem (Q1124351) (← links)
- Testing the universal instance assumption (Q1133903) (← links)
- Data encodings and their costs (Q1139942) (← links)
- The node-deletion problem for hereditary properties is NP-complete (Q1140988) (← links)
- On finding minimal length superstrings (Q1140992) (← links)
- Complexity of dimension three and some related edge-covering characteristics of graphs (Q1143791) (← links)
- On the complexity of computing bilinear forms with \(\{0,1\}\) constants (Q1144927) (← links)
- Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete (Q1146685) (← links)
- Optimization problems and the polynomial hierarchy (Q1152218) (← links)
- Discrete extremal problems (Q1152306) (← links)
- The complexity of a multiprocessor task assignment problem without deadlines (Q1155958) (← links)
- Balancing signed graphs (Q1156154) (← links)
- Optimization and approximation algorithm for placement of records on linear storage devices (Q1158748) (← links)
- Complexity of representation of graphs by set systems (Q1158768) (← links)
- The splittance of a graph (Q1167741) (← links)
- NP-completeness of some generalizations of the maximum matching problem (Q1168728) (← links)
- Planar kernel and Grundy with \(d\leq 3\), \(dout\leq 2\), \(din\leq 2\) are NP- complete (Q1168729) (← links)
- Unit disk graphs (Q1174134) (← links)
- On minimum dominating sets with minimum intersection (Q1174139) (← links)
- Why not negation by fixpoint? (Q1176286) (← links)
- \(\alpha\)-vertex separator is NP-hard even for 3-regular graphs (Q1179551) (← links)
- Computing independent sets in graphs with large girth (Q1183338) (← links)
- Expressing combinatorial optimization problems by linear programs (Q1186549) (← links)
- Reduction of indefinite quadratic programs to bilinear programs (Q1187369) (← links)
- A linear time algorithm for graph partition problems (Q1198016) (← links)
- Finding good approximate vertex and edge partitions is NP-hard (Q1198051) (← links)
- Max-cut in circulant graphs (Q1201272) (← links)
- The NP-completeness of the bandwidth minimization problem (Q1223124) (← links)