相关参考文献
注意:仅列出部分参考文献,下载原文获取全部文献信息。
Article
Computer Science, Hardware & Architecture
Adrien Cambier et al.
Summary: In the context of a telecommunication company that serves as both an infrastructure operator and a service provider, network expansion planning is optimized based on knowledge of subscriber dynamics to prevent unnecessary costs. Subsidies can be used to influence subscriber behavior, and planning must meet strategic guideline requirements. The research proposes a mixed-integer linear programming model with valid inequalities and a heuristic algorithm for numerical evaluation on real instances.
Article
Computer Science, Hardware & Architecture
Alexsander A. de Melo et al.
Summary: The text discusses the NP-completeness of the simple two-commodity integral flow problem in directed and undirected cases. Various proofs and investigations have been conducted to explore the complexity of the problem under different demand scenarios, ultimately providing insights into the problem's complexity.
Article
Computer Science, Hardware & Architecture
Mariia Anapolska et al.
Summary: The minimum color-degree perfect matching problem is proven to be NP-hard on bipartite graphs, but can be solved in polynomial time on specific two-colored complete bipartite graphs. Additionally, polynomial-time algorithms are developed for solving the problem with a fixed number of colors on series-parallel graphs and simple graphs with bounded treewidth.
Article
Computer Science, Hardware & Architecture
S. Raghavan et al.
Summary: This paper investigates the weighted target set selection problem on social networks, proposing algorithms for trees and cycles and deriving corresponding polytope descriptions and sets of valid inequalities. The formulations presented can be applied to arbitrary graphs for solving the WTSS problem.
Article
Computer Science, Hardware & Architecture
Carlos E. Marciano et al.
Summary: This paper discusses the applications of edge reversal scheduling technique in real-world scenarios and proposes algorithms for solving both maximum and minimum concurrency problems. The study shows the general inapproximability of maximum concurrency and introduces approximation algorithms for certain graph classes, while also establishing the relation of minimum concurrency to longest cycles using hardness and inapproximability results, and introducing a new application in assembling musical phrases.
Article
Computer Science, Hardware & Architecture
Naga V. C. Gudapati et al.
Summary: Finding the densest subgraph in a given graph has real-world applications such as determining important regions, similar characteristics, or enhanced interaction. The densest subgraph extraction problem is a non-linear optimization problem, but can be solved in polynomial time by an exact algorithm based on solving max-flow subproblems iteratively. To handle large graphs, heuristic algorithms are needed.
Article
Computer Science, Hardware & Architecture
Artur Tomaszewski et al.
Summary: In this paper, the focus is on optimizing routing in the network while considering limitations on the number of routing configurations that can be used. The proposed solution approach is based on routing cluster generation and provides a tight lower bound on the minimum of a selected objective function.