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

A linear-time certifying algorithm for recognizing generalized series-parallel graphs

DISCRETE APPLIED MATHEMATICS 2023年 325卷 152-171页

作者： Chin, Francis Y. L. Ting, Hing-Fung Tsin, Yung H. Zhang, Yong Univ Hong Kong Dept Comp Sci Hong Kong Peoples R China Univ Windsor Sch Comp Sci Windsor ON N9B 3P4 Canada Chinese Acad Sci Shenzhen Inst Adv Technol Beijing Peoples R China

The problems of recognizing series-parallel graphs, outerplanar graphs, and generalized series-parallel graphs have been studied separately in the past. Efficient algorithms have been presented. However, none of the algorithms are certifying. A certifying algorithm generates, in addition to its answer, a certificate that can be used by a checker (a separate algorithm) to verify the correctness of the answer. The certificate is positive if the answer is 'yes', and is negative if the answer is 'no'. In this paper, an O(|E| + |V |)-time certifying algorithm that simultaneously determines if a graph G = (V, E) is series- parallel, outerplanar, or generalized series-parallel is presented. The positive certificates are a construction sequence for constructing G if G is series-parallel, a generalized construction sequence for constructing G if G is generalized series-parallel but not series-parallel, and the edge set of the exterior boundary of an outerplanar embedding of G if G is outerplanar. The negative certificates are forbidden subgraphs or forbidden structures of G. All these certificates are generated by making only one pass over G after a preprocessing step decomposing G into its biconnected components.(c) 2022 Elsevier B.V. All rights reserved.

关键词： Graph algorithm certifying algorithm Recognition algorithm Ear-decomposition Depth-first search Series-parallel graph Outerplanar graph Generalized series-parallel graph Forbidden structure Certificate Certificate authentication

来源：评论

学校读者我要写书评

暂无评论

A certifying algorithm for Linear (and Integer) Feasibility in Horn Constraint Systems 34th

A Certifying Algorithm for Linear (and Integer) Feasibility ...

引用

34th International Symposium on Logic-Based Program Synthesis and Transformation (LOPSTR)

作者： Wojciechowski, Piotr Subramani, K. West Virginia Univ LDCSEE Morgantown WV 26506 USA

ISBN: (纸本)9783031712937;9783031712944

In this paper, we discuss a certifying version of the Lifting algorithm for Horn constraint systems. Recall that a Horn constraint system (HCS) is a specialized polyhedral system that finds application in a number of domains such as program verification (abstract interpretation) and operations research. HCSs are closely related to Leontief substitution systems. In previous work, it was established that the problem of checking if a Horn polytope is non-empty is polynomial time solvable. However, that algorithm is not certifying in that if the input HCS is infeasible, it does not provide a certificate which attests to the infeasibility of the HCS. Consequently, the output provided by an implementation of the algorithm is not trustworthy. Trustworthiness is an integral aspect of AI systems. The current paper rectifies this issue by modifying the lifting algorithm to make it certifying. In particular, both "yes" - instances and "no"-instances of input HCSs will be certified through appropriate Farkas' variables. However, the increased trustworthiness of the algorithm comes at a cost;the new algorithm is less efficient than its non-certifying counterpart.

关键词： Horn Constraints certifying algorithm Farkas' Lemma Integer Feasibility Linear Feasibility

来源：评论

学校读者我要写书评

暂无评论

A simple certifying algorithm for 3-edge-connectivity

引用

THEORETICAL COMPUTER SCIENCE 2023年第1期951卷

作者： Tsin, Yung H. Univ Windsor Sch Comp Sci Windsor ON N9B 3P4 Canada

A linear-time certifying algorithm for 3-edge-connectivity is presented. Given a connected undirected graph G, if G is 3-edge-connected, the algorithm generates a construction sequence as a positive certificate for G. Otherwise, the algorithm decomposes G into its 3-edge-connected components and generates a construction sequence for each of them as well as the bridges and a cactus representation of the cut-pairs in G as negative certificates. All of these are done by making only one pass over G using an innovative graph contraction technique. Moreover, the graph needs not be 2-edge-connected. The currently best-known algorithm is more complicated as it makes multiple passes over G and uses involved reduction and perturbation techniques rather than just basic graph-theoretic techniques.(c) 2023 Elsevier B.V. All rights reserved.

关键词： certifying algorithm Graph recognition algorithm 3-edge-connected graph 3-edge-connected component Mader construction sequence Cactus representation of cut-pair Certificate Depth-first search

来源：评论

学校读者我要写书评

暂无评论

A certifying and dynamic algorithm for the recognition of proper circular-arc graphs

引用

THEORETICAL COMPUTER SCIENCE 2021年 889卷 105-134页

作者： Soulignac, Francisco J. Univ Nacl Quilmes Dept Ciencia & Tecnol Bernal Buenos Aires Argentina Univ Buenos Aires Fac Ciencias Exactas & Nat Dept Comp Buenos Aires DF Argentina Univ Buenos Aires Inst Invest Ciencias Comp ICC CONICET Buenos Aires DF Argentina

We present a dynamic algorithm for the recognition of proper circular-arc (PCA) graphs, that supports the insertion and removal of vertices (together with its incident edges). The main feature of the algorithm is that it outputs a minimally non-PCA induced subgraph when the insertion of a vertex fails. Each operation cost O(log n + d) time, where nis the number vertices and dis the degree of the modified vertex. When removals are disallowed, each insertion is processed in O(d) time. The algorithm also provides two constant-time operations to query if the dynamic graph is proper Helly (PHCA) or proper interval (PIG). When the dynamic graph is not PHCA (resp. PIG), a minimally non-PHCA (resp. non-PIG) induced subgraph is obtained. (C) 2021 Elsevier B.V. All rights reserved.

关键词： Dynamic representation certifying algorithm Proper circular-arc graphs Proper interval graph Proper Helly circular-arc graphs

来源：评论

学校读者我要写书评

暂无评论

Forbidden structure characterization of circular-arc graphs and a certifying recognition algorithm 15

Forbidden structure characterization of circular-arc graphs ...

引用

Annual ACM-Society for Industrial and Applied Mathmatics Symposium on Discrete algorithms

作者： Mathew Francis Pavol Hell Juraj Stacho Computer Science Unit Indian Statistical Institute School of Computing Science Simon Fraser University IEOR Department Columbia University

ISBN: (纸本)9781510813311

A circular-arc graph is the intersection graph of arcs of a circle. It is a well-studied graph model with numerous natural applications. A certifying algorithm is an algorithm that outputs a certificate, along with its answer (be it positive or negative), where the certificate can be used to easily justify the given answer. While the recognition of circular-arc graphs has been known to be polynomial since the 1980s, no polynomialtime certifying recognition algorithm is known to date, despite such algorithms being found for many subclasses of circular-arc graphs. This is largely due to the fact that a forbidden structure characterization of circulararc graphs is not known, even though the problem has been intensely studied since the seminal work of Klee in the 1960s. In this contribution, we settle this problem. We present the first forbidden structure characterization of circular-arc graphs. Our obstruction has the form of mutually avoiding walks in the graph. It naturally extends a similar obstruction that characterizes interval graphs. As a consequence, we give the first polynomialtime certifying algorithm for the recognition of circulararc graphs.

关键词： Circular-arc graph Forbidden subgraph characterization certifying algorithm Asteroidal triple Invertible pair Interval orientation Transitive orientation Knotting graph circular arc algorithms Recognition (Psychology) Licence Answer Obstruction Line graph Graphical models

来源：评论

学校读者我要写书评

暂无评论

certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs

引用

DISCRETE APPLIED MATHEMATICS 2009年第15期157卷 3216-3230页

作者： Kaplan, Haim Nussbaum, Yahav Tel Aviv Univ Blavatnik Sch Comp Sci IL-69978 Tel Aviv Israel

We give two new linear-time algorithms, one for recognizing proper circular-arc graphs and the other for recognizing unit circular-arc graphs. Both algorithms provide either a model for the input graph, or a certificate that proves that such a model does not exist and can be authenticated in O(n) time. No other previous algorithm for each of these two graph classes provides a certificate for its result. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Proper circular-arc Unit circular-arc certifying algorithm Graph recognition

来源：评论

学校读者我要写书评

暂无评论

Linear-time certifying algorithms for near-graphical sequences

引用

DISCRETE MATHEMATICS 2009年第18期309卷 5703-5713页

作者： Hell, Pavol Kirkpatrick, David Univ British Columbia Dept Comp Sci Vancouver BC V6T 1Z4 Canada Simon Fraser Univ Sch Comp Sci Burnaby BC V5A 1S6 Canada

Asequence (d(1), d(2),....d(n)) of non-negative integers isgraphical if it is the degree sequence of some graph, that is, there exists a graph G on n vertices whose ith vertex has degree d(i), for 1 <= i <= n. The notion of a graphical sequence has a natural reformulation and generalization in terms of factors of complete graphs. If H = (V, E) is a graph and g and f are integer-valued functions on the vertex set V, then a (g, f)-factor of H is a subgraph G = (V, F) of H whose degree at each vertex nu is an element of V lies in the interval vertical bar g(v),f (v)vertical bar. Thus, a (0,1)-factor is just a matching of H and a (1, I)-factor is a perfect matching of H. If H is complete then a (g,f)-factor realizes a degree sequence that is consistent with the sequence of intervals . Graphical sequences have been extensively studied and admit several elegant characterizations. We are interested in extending these characterizations to non-graphical sequences by introducing a natural measure of "near-graphical". We do this in the context of minimally deficient (g,f)-factors of complete graphs. Our main result is a simple lineartime greedy algorithm for constructing minimally deficient (g,f)-factors in complete graphs that generalizes the method of Hakimi and Havel (for constructing (f,f)-factors in complete graphs, when possible). It has the added advantage of producing a certificate of minimum deficiency (through a generalization of the Erdos-Gallai characterization of (f,f)-factors in complete graphs) at no additional cost. (C) 2008 Elsevier B.V. All rights reserved.

关键词： Degree sequence Graphical sequence f-factor (g, f)-factor Graph factor certifying algorithm

来源：评论

学校读者我要写书评

暂无评论

Simple certifying algorithms for variants of the (2,1)-colouring problem 12

Simple certifying algorithms for variants of the (2,1)-colou...

引用

12th Latin-American algorithms, Graphs and Optimization Symposium (LAGOS)

作者： Contreras-Mendoza, Fernando Esteban Hernandez-Cruza, Cesar Univ Nacl Autonoma Mexico Fac Ciencias Mexico City 04510 DF Mexico

A (2, 1)-colouring of a graph is a partition of its vertex set into two independent sets and a clique (any of which may be empty). We present forbidden induced subgraph characterizations for some hereditary graph classes obtained from (2, 1)-colouring by adding restrictions between its parts (e.g., there are no edges between the clique and one of the independent sets). The obtained characterizations yield certifying algorithms to recognize these graph classes, which run in time O(|V| + |E|). All the algorithms presented are straightforward to implement using basic data structures. (C) 2023 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (https://***/licenses/by-nc-nd/4.0)

关键词： certifying algorithm forbidden induced subgraph characterization vertex partition hereditary classes matrix partition

来源：评论

学校读者我要写书评

暂无评论

Simple certifying algorithms for variants of the (2, 1)-colouring problem

引用

Procedia Computer Science 2023年 223卷 292-301页

作者： Fernando Esteban Contreras-Mendoza César Hernández-Cruz Facultad de Ciencias Universidad Nacional Autónoma de México CDMX 04510 México

A (2, 1)-colouring of a graph is a partition of its vertex set into two independent sets and a clique (any of which may be empty). We present forbidden induced subgraph characterizations for some hereditary graph classes obtained from (2, 1)-colouring by adding restrictions between its parts (e.g., there are no edges between the clique and one of the independent sets). The obtained characterizations yield certifying algorithms to recognize these graph classes, which run in time O (| V | + | E |). All the algorithms presented are straightforward to implement using basic data structures.

关键词： certifying algorithm forbidden induced subgraph characterization vertex partition hereditary classes matrix partition 05C75 05C85 68R10 05C15 05C69

来源：评论

学校读者我要写书评

暂无评论

On certifying Instances of Zero-Clairvoyant Scheduling

引用

COMPUTER JOURNAL 2014年第1期57卷 129-137页

作者： Subramani, K. Worthington, James W Virginia Univ LDCSEE Morgantown WV 26506 USA

In this paper, we discuss certifying algorithms for zero-clairvoyant scheduling (ZCS) problems. ZCS problems are a class of real-time scheduling problems defined in the scheduling framework [Subramani, K. (2005) A comprehensive framework for specifying clairvoyance, constraints and periodicity in real-time scheduling. Comput. J., 48, 259-272]. In ZCS, the dispatcher has no knowledge of the execution time of a given job, even after the job has finished executing. A polynomial-time algorithm for ZCS was proposed in previous work of the first author [Subramani, K. (2007) A polynomial time algorithm for zero-clairvoyant scheduling. J. Appl. Logic, 5, 667-680]. However, the algorithm proposed therein is not certifying. The algorithm that we propose in this paper is certifying, in that it provides a structure that certifies the 'yes'-instances and another structure that certifies the 'no'-instances of ZCS problems. These structures make the discovery of implementation errors straightforward and greatly simplify the software development cycle. Moreover, the certifying algorithm has the same running time (asymptotically) as its non-certifying counterpart. We also show that the proposed certifying technique can be used to certify a class of mathematical programs called E-Quantified Polyhedral programs (E-QPPs). However, for E-QPPs, the proposed certifying algorithm has a higher asymptotic running time than its non-certifying counterpart.

关键词： real-time scheduling dispatching clairvoyance certifying algorithm

来源：评论

学校读者我要写书评

暂无评论

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：