On the Computational Complexity of Combinatorial Problems

DOI10.1002/NET.1975.5.1.45zbMath0324.05003OpenAlexW100926944WikidataQ56503916 ScholiaQ56503916MaRDI QIDQ4087195

Richard M. Karp

Publication date: 1975

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.1975.5.1.45

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Deterministic network models in operations research (90B10) 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)

Related Items (only showing first 100 items - show all)

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 ⋮ Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths ⋮ Towards Single Face Shortest Vertex-Disjoint Paths in Undirected Planar Graphs ⋮ Constant Congestion Routing of Symmetric Demands in Planar Directed Graphs ⋮ Optimal node disjoint paths on partial 2-trees: A linear algorithm and polyhedral results ⋮ The parallel complexity of tree embedding problems (extended abstract) ⋮ A hybrid modified-NSGA-II VNS algorithm for the multi-objective critical disruption path problem ⋮ Edge-treewidth: algorithmic and combinatorial properties ⋮ Network reliability: Heading out on the highway ⋮ On undirected two‐commodity integral flow, disjoint paths and strict terminal connection problems ⋮ The Induced Disjoint Paths Problem ⋮ Optimal Surface Flattening ⋮ Finding the edges in optimal Hamiltonian cycles based on frequency quadrilaterals ⋮ A polynomial time algorithm for the triangle packing problem on interval graphs ⋮ Approximating maximum integral multiflows on bounded genus graphs ⋮ Parallel connectivity in edge-colored complete graphs: complexity results ⋮ Unnamed Item ⋮ Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022 ⋮ Using a Geometric Lens to Find \(\boldsymbol{k}\)-Disjoint Shortest Paths ⋮ An integrated rolling horizon and adaptive-refinement approach for disjoint trajectories optimization ⋮ Robust Factorizations and Colorings of Tensor Graphs ⋮ Unnamed Item ⋮ A class of problems of optimal net synthesis ⋮ Technical Note—There’s No Free Lunch: On the Hardness of Choosing a Correct Big-M in Bilevel Optimization ⋮ Connectivity and inference problems for temporal networks ⋮ On the computational complexity of centers locating in a graph ⋮ Unnamed Item ⋮ Slightly Superexponential Parameterized Problems ⋮ Induced Disjoint Paths in Claw-Free Graphs ⋮ Fairness in routing and load balancing ⋮ A hard problem that is almost always easy ⋮ The adjacency relation on the traveling salesman polytope is NP-Complete ⋮ Unnamed Item ⋮ NP-completeness of the Eulerian walk problem for a multiple graph ⋮ Packing \(K_r\)s in bounded degree graphs ⋮ The polynomial randomized algorithm to compute bounded degree graph for TSP based on frequency quadrilaterals ⋮ Paths and Trails in Edge-Colored Graphs ⋮ Disjoint paths and connected subgraphs for \(H\)-free graphs ⋮ Disjoint paths and connected subgraphs for \(H\)-free graphs ⋮ On the approximability of time disjoint walks ⋮ Walking through waypoints ⋮ NP-Complete operations research problems and approximation algorithms ⋮ New Hardness Results for Routing on Disjoint Paths ⋮ Maximisation globale de la norme euclidienne sur un compact : résolution approchée par utilisation des problèmes projetés ⋮ Unnamed Item ⋮ An Approximation Algorithm for Fully Planar Edge-Disjoint Paths ⋮ Unnamed Item ⋮ Paths of Bounded Length and Their Cuts: Parameterized Complexity and Algorithms ⋮ The Directed Disjoint Shortest Paths Problem ⋮ An ideal column algorithm for integer programs with special ordered sets of variables ⋮ Unnamed Item ⋮ A Unified Framework for Multistage Mixed Integer Linear Optimization ⋮ Disjoint Paths—A Survey ⋮ Analysis of Optimal Sets of Survivable Paths in Undirected Simple Graph Applicable for Optical Networks ⋮ A quick method to compute sparse graphs for traveling salesman problem using random frequency quadrilaterals ⋮ Chordless paths through three vertices ⋮ Graph minors. VI. Disjoint paths across a disc ⋮ New mixed-integer linear programming model for solving the multidimensional multi-way number partitioning problem ⋮ A modified greedy heuristic for the set covering problem with improved worst case bound ⋮ Lagrangean decomposition/relaxation for the routing and wavelength assignment problem ⋮ An efficient algorithm for \(k\)-pairwise disjoint paths in star graphs ⋮ On residual approximation in solution extension problems ⋮ Induced disjoint paths in circular-arc graphs in linear time ⋮ Rooted routing in the plane ⋮ The complexity of induced minors and related problems ⋮ Paths and trails in edge-colored graphs ⋮ 1.5-approximation algorithm for the 2-convex recoloring problem ⋮ Finding disjoint paths with related path costs ⋮ Interior-point methods: An old and new approach to nonlinear programming ⋮ Optimal product design using conjoint analysis: Computational complexity and algorithms ⋮ Graph factors and factorization: 1985--2003: a survey ⋮ The power of cut-based parameters for computing edge-disjoint paths ⋮ Some recent progress and applications in graph minor theory ⋮ Quota travelling salesman problem with passengers, incomplete ride and collection time optimization by ant-based algorithms ⋮ Linking four vertices in graphs of large connectivity ⋮ Simple undirected two-commodity integral flow with a unitary demand ⋮ An opposition-based memetic algorithm for the maximum quasi-clique problem ⋮ Total coloring and total matching: polyhedra and facets ⋮ Optimal partitions ⋮ The disjoint shortest paths problem ⋮ Sufficient and necessary conditions for an edge in the optimal Hamiltonian cycle based on frequency quadrilaterals ⋮ Complexity results for scheduling chains on a single machine ⋮ Complexity of dimension three and some related edge-covering characteristics of graphs ⋮ The disjoint paths problem in quadratic time ⋮ A linear time algorithm for the induced disjoint paths problem in planar graphs ⋮ Complexity of spanning tree problems: Part I ⋮ The complexity of minimum convex coloring ⋮ The \(k\)-in-a-path problem for claw-free graphs ⋮ Vertex-edge domination in cubic graphs ⋮ On generalized matching problems ⋮ Discrete extremal problems ⋮ On shortest disjoint paths in planar graphs ⋮ Kernel bounds for disjoint cycles and disjoint paths ⋮ Degree conditions for the existence of vertex-disjoint cycles and paths: a survey ⋮ Multiflow Feasibility: An Annotated Tableau ⋮ The 1-fixed-endpoint path cover problem is Polynomial on interval graphs ⋮ The complexity of register allocation ⋮ 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

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