On the Computational Complexity of Combinatorial Problems

Software, source code, etc. for problems pertaining to combinatorics (05-04) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35) Analysis of algorithms and problem complexity (68Q25) Deterministic network models in operations research (90B10)

Cited in

(only showing first 100 items - show all)

Disjoint paths in symmetric digraphs
Scheduling subject to resource constraints: Classification and complexity
Graph minors. VI. Disjoint paths across a disc
Optimal product design using conjoint analysis: Computational complexity and algorithms
Optimal partitions
Complexity results for scheduling chains on a single machine
Complexity of dimension three and some related edge-covering characteristics of graphs
Complexity of spanning tree problems: Part I
On generalized matching problems
Discrete extremal problems
On the relationship between the biconnectivity augmentation and traveling salesman problems
An appraisal of computational complexity for operations researchers
Path-matching problems
Scheduling with neural networks -- the case of the Hubble Space Telescope
On the complexity of finding iso- and other morphisms for partial \(k\)- trees
General vertex disjoint paths in series-parallel graphs
The densest hemisphere problem
Even initial feedback vertex set problem is NP-complete
An interactive decision support system for the resource constrained scheduling problem
Generalized partitions of graphs
A weighted graph polynomial from chromatic invariants of knots
A new optimal algorithm for backbone topology design in communications networks
A modified greedy heuristic for the set covering problem with improved worst case bound
Rooted routing in the plane
The complexity of induced minors and related problems
Interior-point methods: An old and new approach to nonlinear programming
The disjoint shortest paths problem
On residual approximation in solution extension problems
1.5-approximation algorithm for the 2-convex recoloring problem
Degree conditions for the existence of vertex-disjoint cycles and paths: a survey
New algorithms for maximum disjoint paths based on tree-likeness
Using dual network bounds in algorithms for solving generalized set packing/partitioning problems
Efficient graph automorphism by vertex partitioning
On the NP-hardness of edge-deletion and -contraction problems
The 1-fixed-endpoint path cover problem is Polynomial on interval graphs
Improved algorithms for finding length-bounded two vertex-disjoint paths in a planar graph and minmax \(k\) vertex-disjoint paths in a directed acyclic graph
A polyhedral approach to an integer multicommodity flow problem
On the inapproximability of disjoint paths and minimum Steiner forest with bandwidth constraints
Steady states in the scheduling of discrete-time systems
On structural parameterizations of the edge disjoint paths problem
The frequency of the optimal Hamiltonian cycle computed with frequency quadrilaterals for traveling salesman problem
The distribution of edge-frequencies computed with frequency quadrilaterals for traveling salesman problem
Forbidden subgraphs for existences of (connected) 2-factors of a graph
New mixed-integer linear programming model for solving the multidimensional multi-way number partitioning problem
An opposition-based memetic algorithm for the maximum quasi-clique problem
Vertex-edge domination in cubic graphs
The (theta, wheel)-free graphs. IV: Induced paths and cycles
Solving an integrated scheduling and routing problem with inventory, routing and penalty costs
Edge clique partition in \((k,\ell)\)-graphs
Variable neighbourhood search for the minimum labelling Steiner tree problem
A polynomial solution to the \(k\)-fixed-endpoint path cover problem on proper interval graphs
Two disjoint shortest paths problem with non-negative edge length
The undirected two disjoint shortest paths problem
Disjoint dominating and 2-dominating sets in graphs
A lower bound on the tree-width of graphs with irrelevant vertices
Paths and trails in edge-colored graphs
Simple undirected two-commodity integral flow with a unitary demand
Sufficient and necessary conditions for an edge in the optimal Hamiltonian cycle based on frequency quadrilaterals
The \(k\)-in-a-path problem for claw-free graphs
The complexity of register allocation
Packing triangles in low degree graphs and indifference graphs
Sources of complexity in subset choice
Highly linked graphs
On the complexity of the planar directed edge-disjoint paths problem
Induced disjoint paths in circular-arc graphs in linear time
The power of cut-based parameters for computing edge-disjoint paths
Quota travelling salesman problem with passengers, incomplete ride and collection time optimization by ant-based algorithms
Linking four vertices in graphs of large connectivity
Total coloring and total matching: polyhedra and facets
Lagrangean decomposition/relaxation for the routing and wavelength assignment problem
An efficient algorithm for k-pairwise disjoint paths in star graphs
Multiflow Feasibility: An Annotated Tableau
Special frequency quadrilaterals and an application
New hardness results for routing on disjoint paths
Analysis of Optimal Sets of Survivable Paths in Undirected Simple Graph Applicable for Optical Networks
Towards single face shortest vertex-disjoint paths in undirected planar graphs
The Induced Disjoint Paths Problem
Optimal Surface Flattening
Paths of bounded length and their cuts: parameterized complexity and algorithms
An ideal column algorithm for integer programs with special ordered sets of variables
Disjoint Paths—A Survey
A class of problems of optimal net synthesis
On the computational complexity of centers locating in a graph
scientific article; zbMATH DE number 3770947 (Why is no real title available?)
Worst-Case Analysis of Network Design Problem Heuristics
The Complexity of Coloring Circular Arcs and Chords
Exact Solution of Systems of Linear Equations with Iterative Methods
The disjoint paths problem in quadratic time
A linear time algorithm for the induced disjoint paths problem in planar graphs
The complexity of minimum convex coloring
The adjacency relation on the traveling salesman polytope is NP-Complete
NP-Complete operations research problems and approximation algorithms
Maximisation globale de la norme euclidienne sur un compact : résolution approchée par utilisation des problèmes projetés
On shortest disjoint paths in planar graphs
Paths of bounded length and their cuts: parameterized complexity and algorithms
Constant congestion routing of symmetric demands in planar directed graphs
Confronting intractability via parameters
Optimal node disjoint paths on partial 2-trees: A linear algorithm and polyhedral results
Nearly tight approximation bounds for vertex cover on dense \(k\)-uniform \( k\)-partite hypergraphs
Finding disjoint paths in split graphs

This page was built for publication: On the Computational Complexity of Combinatorial Problems

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