检索结果-内蒙古大学图书馆

Feedback vertex set reconfiguration in planar graphs

THEORETICAL COMPUTER SCIENCE 2023年 979卷

作者： Bousquet, Nicolas Hommelsheim, Felix Kobayashi, Yusuke Muehlenthaler, Moritz Suzuki, Akira Univ Lyon 1 Univ Lyon CNRS LIRISUMR 5205 Lyon France Univ Bremen Fac Math & Comp Sci Bremen Germany Kyoto Univ Res Inst Math Sci Kyoto Japan Univ Grenoble Alpes Lab G SCOP Grenoble France Tohoku Univ Grad Sch Informat Sci Sendai Japan

We study the complexity of deciding whether for two given feedback vertex sets of a graph there is a step-by-step transformation between them, such that for each feedback vertex set in the transformation, the next one is obtained by exchanging a single vertex. We give a classification of the complexity of this question for planar graphs in terms of the maximum degree. We show that for planar graphs of maximum degree at most three the problem is tractable because there always exists a transformation, while it is PSPACE-complete when the maximum degree is at most four. The positive side of the classification extends to K-3,K-3-minor-free graphs of maximum degree three. We then consider the Matroid Parity problem, which generalizes feedback vertex sets in graphs of maximum degree three as well as matchings and spanning trees in general graphs. Generalizing known results for the latter two we show that there always exists a transformation between any two non -maximum independent parity sets.(c) 2023 Elsevier B.V. All rights reserved.

关键词： Feedback vertex set Combinatorial reconfiguration polynomial-time algorithm Planar graph Matroid parity

来源：评论

学校读者我要写书评

暂无评论

A network flow approach to a common generalization of Clar and Fries numbers

引用

DISCRETE MATHEMATICS 2024年第11期347卷

作者： Berczi-Kovacs, Erika Frank, Andras HUN REN Alfred Renyi Inst Math Budapest Hungary HUN REN ELTE Egervary Res Grp Combinatorial Optimi Budapest Hungary Eotvos Lorand Univ Dept Operat Res Budapest Hungary

Clar number and Fries number are two thoroughly investigated parameters of plane graphs emerging from mathematical chemistry to measure stability of organic molecules. First, we introduce a common generalization of these two concepts for bipartite plane graphs, and then we extend it further to the notion of source-sink pairs of subsets of nodes in a general (not necessarily planar) directed graph. The main result is a min-max formula for the maximum weight of a source-sink pair. The proof is based on the recognition that the convex hull of source-sink pairs can be obtained as the projection of a network tension polyhedron. The construction makes it possible to apply any standard cheapest network flow algorithm to compute both a maximum weight source-sink pair and a minimizer of the dual optimization problem formulated in the min-max theorem. As a consequence, our approach gives rise to the first purely combinatorial, strongly polynomial algorithm to compute a largest (or even a maximum weight) Fries-set of a perfectly matchable plane bipartite graph and an optimal solution to the dual minimization problem. (c) 2024 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.

关键词： Clar number Fries number polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Defective incidence coloring of graphs

引用

APPLIED MATHEMATICS AND COMPUTATION 2023年第1期443卷

作者： Bi, Huimin Zhang, Xin Xidian Univ Sch Math & Stat Xian 710071 Peoples R China

We define the d-defective incidence chromatic number of a graph, generalizing the notion of incidence chromatic number, and determine it for some classes of graphs including trees, complete bipartite graphs, complete graphs, and outerplanar graphs. Fast algorithms for constructing the optimal d-defective incidence colorings of those graphs are presented. (c) 2022 Elsevier Inc. All rights reserved.

关键词： Incidence coloring Defective coloring Latin square Outerplanar graph polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Interference-free walks in time: temporally disjoint paths

引用

AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS 2023年第1期37卷 1-1页

作者： Klobas, Nina Mertzios, George B. Molter, Hendrik Niedermeier, Rolf Zschoche, Philipp Univ Durham Dept Comp Sci Upper Mountjoy CampusStockton Rd Durham DH1 3LE England Ben Gurion Univ Negev Dept Ind Engn & Management David Ben Gurion Blvd IL-84105 Beer Sheva Israel TU Berlin Fac 4 Algorithm & Computat Complex Ernst Reuter Pl 7 D-10587 Berlin Germany

We investigate the computational complexity of finding temporally disjoint paths and walks in temporal graphs. There, the edge set changes over discrete time steps. Temporal paths and walks use edges that appear at monotonically increasing time steps. Two paths (or walks) are temporally disjoint if they never visit the same vertex at the same time;otherwise, they interfere. This reflects applications in robotics, traffic routing, or finding safe pathways in dynamically changing networks. At one extreme, we show that on general graphs the problem is computationally hard. The path version is NP-hard even if we want to find only two temporally disjoint paths. The walk version is W-hard (Klobas in IJCAI 4090-4096, 2021) when parameterized by the number of walks. However, it is polynomial-time solvable for any constant number of walks. At the other extreme, restricting the input temporal graph to have a path as underlying graph, quite counter-intuitively, we find NP-hardness in general but also identify natural tractable cases.

关键词： Temporal graph Temporal path NP-complete problem Parameterized complexity polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Cost-aware scheduling on uniform parallel machines

引用

COMPUTERS & INDUSTRIAL ENGINEERING 2022年 167卷

作者： Kononov, Alexander Lushchakova, Irina Sobolev Inst Math Koptyuga 4 Novosibirsk 630090 Russia Belarusian State Univ Informat & Radioelect P Brovki St 6 Minsk 220013 BELARUS

We consider scheduling problems with uniform parallel machines to minimize the sum of the total (weighted) completion time and the total cost for usage of machines. A cost density function is given for each machine in advance. Integrating the cost density function for the time period(s) when the machine is busy, one obtains the cost of using this machine in a schedule. We suggest the classification of the problems under consideration according to the type of the cost density functions. The notions of a simple cost density function and an almost concave cost density function are introduced. For these types of cost density functions, we investigate the properties of optimal schedules. Based on these properties, we develop two families of exact pseudo-polynomial DP algorithms. For the case of two uniform machines, we present an FPTAS. Besides, a polynomial-solvable case of the problem is considered.

关键词： Uniform parallel machines Total weighted completion time Total machine cost FPTAS polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

A WEIGHTED LINEAR MATROID PARITY algorithm

引用

SIAM JOURNAL ON COMPUTING 2022年第2期51卷 STOC17-238-STOC17-280页

作者： Iwata, Satoru Kobayashi, Yusuke Univ Tokyo Dept Math Informat Tokyo 1138656 Japan Kyoto Univ Res Inst Math Sci Kyoto 6068502 Japan

The matroid parity (or matroid matching) problem, introduced as a common generalization of matching and matroid intersection problems, is so general that it requires an exponential number of oracle calls. Nevertheless, Lov\'asz [Acta Sci. Math., 42 (1980), pp. 121-131] showed that this problem admits a min-max formula and a polynomial algorithm for linearly represented matroids. Since then efficient algorithms have been developed for the linear matroid parity problem. In this paper, we present a combinatorial, deterministic, polynomial-time algorithm for the weighted linear matroid parity problem. The algorithm builds on a polynomial matrix formulation using Pfaffian and adopts a primal-dual approach based on the augmenting path algorithm of Gabow and Stallmann [Combinatorica, 6 (1986), pp. 123-150] for the unweighted problem.

关键词： linear matroid parity matching polynomial-time algorithm Pfaffian primal-dual approach

来源：评论

学校读者我要写书评

暂无评论

On Reachable Assignments in Cycles 7th

On Reachable Assignments in Cycles

引用

7th International Conference on algorithmic Decision Theory (ADT)

作者： Mueller, Luis Bentert, Matthias TU Berlin Algorithm & Computat Complex Berlin Germany

ISBN: (纸本)9783030877569;9783030877552

The efficient and fair distribution of indivisible resources among agents is a common problem in the field of Multi-Agent-Systems. We consider a graph-based version of this problem called REACHABLE ASSIGNMENT, introduced by Gourves, Lesca, and Wilczynski [IJCAI, 2017]. The input for this problem consists of a set of agents, a set of objects, the agent's preferences over the objects, a graph with the agents as vertices and edges encoding which agents can trade resources with each other, and an initial and a target distribution of the objects, where each agent owns exactly one object in each distribution. The question is then whether the target distribution is reachable via a sequence of rational trades. A trade is rational when the two participating agents are neighbors in the graph and both obtain an object they prefer over the object they previously held. We show that REACHABLE ASSIGNMENT is solvable in O(n(3)) time when the input graph is a cycle with n vertices.

关键词： Multi-Agent Systems Resource allocation polynomial-time algorithm Reduction to 2-SAT

来源：评论

学校读者我要写书评

暂无评论

Adapting Stable Matchings to Forced and Forbidden Pairs 23

Adapting Stable Matchings to Forced and Forbidden Pairs

引用

Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems

作者： Niclas Boehmer Klaus Heeger Technische Universität Berlin Berlin Germany

ISBN: (纸本)9781450394321

We introduce the problem of adapting a stable matching to forced and forbidden pairs. Specifically, given a stable matching M1, a set Q of forced pairs, and a set P of forbidden pairs, we want to find a stable matching that includes all pairs from Q, no pair from P, and that is as close as possible to M1. We study this problem in four classical stable matching settings: Stable Roommates (with Ties) and Stable Marriage (with Ties).As our main contribution, we employ the theory of rotations for Stable Roommates to develop a polynomial-time algorithm for adapting Stable Roommates matchings to forced pairs. In contrast to this, we show that the same problem for forbidden pairs is NP-hard. However, our polynomial-time algorithm for the case of only forced pairs can be extended to a fixed-parameter tractable algorithm with respect to the number of forbidden pairs when both forced and forbidden pairs are present. Moreover, we also study the setting where preferences contain ties. Here, depending on the chosen stability criterion, we show either that our algorithmic results can be extended or that formerly tractable problems become intractable.

关键词： FPT NP-hardness incremental algorithms W[1]-hardness forced and forbidden pairs polynomial-time algorithm stable marriage rotations stable roommates

来源：评论

学校读者我要写书评

暂无评论

Vertex Cover at Distance on H-Free Graphs 32nd

Vertex Cover at Distance on <i>H</i>-Free Graphs

引用

32nd International Workshop on Combinatorial algorithms (IWOCA)

作者： Dallard, Clement Krbezlija, Mirza Milanic, Martin Univ Primorska FAMNIT Koper Slovenia Univ Primorska IAM Koper Slovenia

ISBN: (纸本)9783030799878;9783030799861

The question of characterizing graphs H such that the VERTEX COVER problem is solvable in polynomial time in the class of H-free graphs is notoriously difficult and still widely open. We completely solve the corresponding question for a distance-based generalization of vertex cover called distance-k vertex cover, for any positive integer k. In this problem the task is to determine, given a graph G and an integer l, whether G contains a set of at most l vertices such that each edge of G is at distance at most k from a vertex in the set. We show that for all k >= 1 and all graphs H, the distance-k vertex cover problem is solvable in polynomial time in the class of H-free graphs if H is an induced subgraph of P2k+2 + sP(max{k,2}) for some s >= 0, and NP-complete otherwise.

关键词： Distance-k Vertex Cover H-free graph NP-completeness polynomial-time algorithm Dichotomy

来源：评论

学校读者我要写书评

暂无评论

Combinatorics and algorithms for Quasi-chain Graphs 32nd

Combinatorics and Algorithms for Quasi-chain Graphs

引用

32nd International Workshop on Combinatorial algorithms (IWOCA)

作者： Alecu, Bogdan Atminas, Aistis Lozin, Vadim Malyshev, Dmitriy Univ Warwick Math Inst Coventry CV4 7AL W Midlands England Xian Jiaotong Liverpool Univ Dept Math Sci 111 Renai Rd Suzhou 215123 Peoples R China Natl Res Univ Higher Sch Econ Lab Algorithms & Technol Networks Anal 136 Rodionova Str Nizhnii Novgorod 603093 Russia Natl Res Lobachevsky State Univ Nizhny Novgorod 23 Gagarina Ave Nizhnii Novgorod 603950 Russia

ISBN: (纸本)9783030799878;9783030799861

The class of quasi-chain graphs is an extension of the well-studied class of chain graphs. The latter class enjoys many nice and important properties, such as bounded clique-width, implicit representation, well-quasi-ordering by induced subgraphs, etc. The class of quasi-chain graphs is substantially more complex. In particular, this class is not well-quasi-ordered by induced subgraphs, and the clique-width is not bounded in it. In the present paper, we show that the universe of quasi-chain graphs is at least as complex as the universe of permutations by establishing a bijection between the class of all permutations and a subclass of quasi-chain graphs. This implies, in particular, that the induced subgraph isomorphism problem is NP-complete for quasi-chain graphs. On the other hand, we propose a decomposition theorem for quasi-chain graphs that implies an implicit representation for graphs in this class and efficient solutions for some algorithmic problems that are generally intractable.

关键词： Bipartite chain graphs Implicit representation polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：