On the Computational Complexity of Combinatorial Problems

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

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

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, The adjacency relation on the traveling salesman polytope is NP-Complete, Unnamed Item, 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, On the relationship between the biconnectivity augmentation and traveling salesman problems, A state-of-the-art review of parallel-machine scheduling research, Paths of bounded length and their cuts: parameterized complexity and algorithms, Confronting intractability via parameters, The (theta, wheel)-free graphs. IV: Induced paths and cycles, An appraisal of computational complexity for operations researchers, A polyhedral approach to an integer multicommodity flow problem, On the inapproximability of disjoint paths and minimum Steiner forest with bandwidth constraints, Nearly tight approximation bounds for vertex cover on dense \(k\)-uniform \( k\)-partite hypergraphs, Finding disjoint paths in split graphs, Special Frequency Quadrilaterals and an Application, Optimal parallel algorithms for path problems on planar graphs, Solving an integrated scheduling and routing problem with inventory, routing and penalty costs, Unrelated parallel machine scheduling -- perspectives and progress, Path-matching problems, Edge clique partition in \((k,\ell)\)-graphs, The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs, Packing triangles in low degree graphs and indifference graphs, 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, Sources of complexity in subset choice, Induced disjoint paths problem in a planar digraph, Steady states in the scheduling of discrete-time systems, Complexity of pairwise shortest path routing in the grid, On the complexity of interval scheduling with a resource constraint, Minimal multicut and maximal integer multiflow: a survey, 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, Multiflows in symmetric digraphs, Computing simple circuits from a set of line segments, New algorithms for maximum disjoint paths based on tree-likeness, The densest hemisphere problem, On structural parameterizations of the edge disjoint paths problem, The frequency of the optimal Hamiltonian cycle computed with frequency quadrilaterals for traveling salesman problem, Disjoint paths in symmetric digraphs, Two disjoint shortest paths problem with non-negative edge length, The undirected two disjoint shortest paths problem, Even initial feedback vertex set problem is NP-complete, Disjoint dominating and 2-dominating sets in graphs, Induced disjoint paths in AT-free graphs, Using dual network bounds in algorithms for solving generalized set packing/partitioning problems, A lower bound on the tree-width of graphs with irrelevant vertices, An interactive decision support system for the resource constrained scheduling problem, Generalized partitions of graphs, Highly linked graphs, Efficient graph automorphism by vertex partitioning, On the NP-hardness of edge-deletion and -contraction problems, A weighted graph polynomial from chromatic invariants of knots, The distribution of edge-frequencies computed with frequency quadrilaterals for traveling salesman problem, Scheduling subject to resource constraints: Classification and complexity, Edge-contraction problems, A new optimal algorithm for backbone topology design in communications networks, On the complexity of the planar directed edge-disjoint paths problem, Forbidden subgraphs for existences of (connected) 2-factors of a graph, A decomposition approach to multi-project scheduling, Properties of optimal survivable paths in a graph