On the Computational Complexity of Combinatorial Problems

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

Cited in

(only showing first 100 items - show all)

A polyhedral approach to an integer multicommodity flow problem
scientific article; zbMATH DE number 7278041 (Why is no real title available?)
Multicommodity network flows: a survey. I: Applications and formulations
Paths and Trails in Edge-Colored Graphs
A weighted graph polynomial from chromatic invariants of knots
A class of problems of optimal net synthesis
Special frequency quadrilaterals and an application
Analysis of Optimal Sets of Survivable Paths in Undirected Simple Graph Applicable for Optical Networks
Edge-contraction problems
An Approximation Algorithm for Fully Planar Edge-Disjoint Paths
The Directed Disjoint Shortest Paths Problem
Complexity of dimension three and some related edge-covering characteristics of graphs
Finding the edges in optimal Hamiltonian cycles based on frequency quadrilaterals
A polynomial time algorithm for the triangle packing problem on interval graphs
The complexity of minimum convex coloring
Path-matching problems
Approximation algorithm for prize-collecting weighted set cover with fairness constraints
The complexity of register allocation
Algorithms and hardness results for the (3, 1)-cover problem
The disjoint shortest paths problem
The non-stop disjoint trajectories problem
The minimum clique routing problem on cycles
Solving an integrated scheduling and routing problem with inventory, routing and penalty costs
Even initial feedback vertex set problem is NP-complete
Approximating maximum integral multiflows on bounded genus 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
The disjoint paths problem in quadratic time
Minimal multicut and maximal integer multiflow: a survey
On the inapproximability of disjoint paths and minimum Steiner forest with bandwidth constraints
Generalized partitions of graphs
Some polynomial subclasses of the Eulerian walk problem for a multiple graph
Steady states in the scheduling of discrete-time systems
Interior-point methods: An old and new approach to nonlinear programming
Complexity of pairwise shortest path routing in the grid
The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs
The undirected two disjoint shortest paths problem
Clique factors in pseudorandom graphs
On generalized matching problems
Approximating maximum integral multiflows on bounded genus graphs
Paths and trails in edge-colored graphs
Opinion diffusion in graphs: an adversarial approach
Multiflows in symmetric digraphs
Parallel connectivity in edge-colored complete graphs: complexity results
An interactive decision support system for the resource constrained scheduling problem
On residual approximation in solution extension problems
On the NP-hardness of edge-deletion and -contraction problems
A quick method to compute sparse graphs for traveling salesman problem using random frequency quadrilaterals
A state-of-the-art review of parallel-machine scheduling research
Worst-Case Analysis of Network Design Problem Heuristics
Edge clique partition in \((k,\ell)\)-graphs
Optimal node disjoint paths on partial 2-trees: A linear algorithm and polyhedral results
Disjoint paths in symmetric digraphs
An efficient algorithm for k-pairwise disjoint paths in star graphs
Rooted routing in the plane
On the complexity of the planar directed edge-disjoint paths problem
Slightly superexponential parameterized problems
Computing simple circuits from a set of line segments
Linking four vertices in graphs of large connectivity
scientific article; zbMATH DE number 7561324 (Why is no real title available?)
The Induced Disjoint Paths Problem
Fairness in routing and load balancing
1.5-approximation algorithm for the 2-convex recoloring problem
Scheduling subject to resource constraints: Classification and complexity
Using dual network bounds in algorithms for solving generalized set packing/partitioning problems
Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022
An integrated rolling horizon and adaptive-refinement approach for disjoint trajectories optimization
Kernel bounds for disjoint cycles and disjoint paths
Search-space reduction via essential vertices
Technical note -- There's no free lunch: on the hardness of choosing a correct big-M in bilevel optimization
On structural parameterizations of the edge disjoint paths problem
Constant congestion routing of symmetric demands in planar directed graphs
Connectivity and inference problems for temporal networks
Forbidden subgraphs for existences of (connected) 2-factors of a graph
The 1-fixed-endpoint path cover problem is Polynomial on interval graphs
Discrete extremal problems
Optimal partitions
An ideal column algorithm for integer programs with special ordered sets of variables
A new optimal algorithm for backbone topology design in communications networks
An opposition-based memetic algorithm for the maximum quasi-clique problem
scientific article; zbMATH DE number 2230273 (Why is no real title available?)
Paths of bounded length and their cuts: parameterized complexity and algorithms
A hybrid modified-NSGA-II VNS algorithm for the multi-objective critical disruption path problem
Edge-treewidth: algorithmic and combinatorial properties
Tight approximation and kernelization bounds for vertex-disjoint shortest paths
Shortest two disjoint paths in conservative graphs
Multicommodity information flow through quantum annealer
Sources of complexity in subset choice
Some recent progress and applications in graph minor theory
Paths of bounded length and their cuts: parameterized complexity and algorithms
Optimal product design using conjoint analysis: Computational complexity and algorithms
Disjoint Paths—A Survey
New algorithms for maximum disjoint paths based on tree-likeness
A polynomial solution to the \(k\)-fixed-endpoint path cover problem on proper interval graphs
A unified framework for multistage mixed integer linear optimization
Using a geometric Lens to find k disjoint shortest paths
The frequency of the optimal Hamiltonian cycle computed with frequency quadrilaterals for traveling salesman problem
Degree conditions for the existence of vertex-disjoint cycles and paths: a survey
The polynomial randomized algorithm to compute bounded degree graph for TSP based on frequency quadrilaterals
Confronting intractability via parameters
NP-Complete operations research problems and approximation algorithms

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)