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

39th International Symposium on Mathematical Foundations of Computer Science (MFCS)

作者： Kriege, Nils Mutzel, Petra Tech Univ Dortmund Dept Comp Sci Dortmund Germany

ISBN: (纸本)9783662444658;9783662444641

The complexity of the maximum common subgraph problem in partial k-trees is still largely unknown. We consider the restricted case, where the input graphs are k-connected partial k-trees and the common subgraph is required to be k-connected. For biconnected outerplanar graphs this problem is solved and the general problem was reported to be tractable by means of tree decomposition techniques. We discuss key obstacles of tree decompositions arising for common subgraph problems that were ignored by previous algorithms and do not occur in outerplanar graphs. We introduce the concept of potential separators, i.e., separators of a subgraph to be searched that not necessarily are separators of the input graph. We characterize these separators and propose a polynomial time solution for series-parallel graphs based on SP-trees.

关键词： Tree decomposition maximum common subgraph series-parallel graph

来源：评论

学校读者我要写书评

暂无评论

BOUNDING THE NUMBER OF REDUCED TREES, COgraphS, AND series-parallel graphS BY COMPRESSION

引用

DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS 2013年第2期5卷 1360001-1-1360001-14页

作者： Uno, Takeaki Uehara, Ryuhei Nakano, Shin-Ichi Natl Inst Informat Chiyoda Ku 2-1-2 Hitotsubashi Tokyo 1018430 Japan Japan Adv Inst Sci & Technol Sch Informat Sci Nomi Ishikawa 9231292 Japan Gunma Univ Fac Engn Dept Comp Sci Gunma 3768515 Japan

We give an efficient encoding and decoding scheme for computing a compact representation of a graph in one of unordered reduced trees, cographs and series-parallel graphs. The unordered reduced trees are rooted trees in which (i) the ordering of children of each vertex does not matter, and (ii) no vertex has exactly one child. This is one of basic models frequently used in many areas. Our algorithm computes a bit string of length 2l - 1 for a given unordered reduced tree with l >= 1 leaves in O(l) time, whereas a known folklore algorithm computes a bit string of length 2n-2 for an ordered tree with n vertices. Note that in an unordered reduced tree, l >= n < 2l holds. To the best of our knowledge this is the first of such a compact representation for unordered reduced trees. From the theoretical point of view, the length of the representation gives us an upper bound of the number of unordered reduced trees with l leaves. Precisely, the number of unordered reduced trees with l leaves is at most 2(2l-2) for l >= 1. Moreover, the encoding and decoding can be done in linear time. Therefore, from the practical point of view, our representation is also useful to store a lot of unordered reduced trees efficiently. We also apply the scheme for computing a compact representation to cographs and series-parallel graphs. We show that each of cographs with n vertices has a compact representation in 2n - 1 bits, and the number of cographs with n vertices is at most 2(2n-1). The resulting number is close to the number of cographs with n vertices obtained by the enumeration for small n that approximates Cd-n/n(3)/(2), where C = 0.4126 ... and d = 3.5608 ... . series-parallel graphs are well-investigated in the context of the graphs of bounded treewidth. We give a method to represent a series-parallel graph with m edges in [2.5285m - 2] bits. Hence the number of series-parallel graphs with m edges is at most 2([2.5285m-2]). As far as the authors know, this is the first non-trivial r

关键词： Cograph compact representation counting encoding/decoding scheme series-parallel graph unordered reduce tree

来源：评论

学校读者我要写书评

暂无评论

A New Formula for the Number of Labeled series-parallel graphs

引用

Journal of Mathematical Sciences (United States) 2023年第5期277卷 718-721页

作者： Voblyi, V.A. Russian Institute for Scientific and Technical Information Moscow Russian Federation

A series-parallel graph is a graph that does not contain a complete graph with four vertices as a minor. A new explicit simpler formula for the number of labeled series-parallel biconnected graphs with a given number ... 详细信息

关键词： 05C30 2-connected graph enumeration explicit formula labeled graph series-parallel graph

来源：评论

学校读者我要写书评

暂无评论

Adjacent Strong Edge Chromatic Number of series-parallel graphs

引用

Journal of Mathematical Research and Exposition 2005年第2期25卷 267-278页

作者：王淑栋庞善臣许进山东科技大学信息科学与工程学院山东泰安271019 华中科技大学控制科学与工程系湖北武汉430074

In this paper, we will study the adjacent strong edge coloring of series-parallel graphs, and prove that series-parallel graphs of △(G) = 3 and 4 satisfy the conjecture of adjacent strong edge coloring using the double inductions and the method of exchanging colors from the aspect of configuration property. For series-parallel graphs of △(G) ≥ 5, △(G) ≤ x'as(G) ≤ △(G) + 1. Moreover, x'as(G) = △(G) + 1 if and only if it has two adjacent vertices of maximum degree, where △(G) and X'as(G) denote the maximum degree and the adjacent strong edge chromatic number of graph G respectively.

关键词： series-parallel graph adjacent strong edge coloring adjacent strong edge chromatic number.

来源：评论

学校读者我要写书评

暂无评论

The circular chromatic numbers of signed series-parallel graphs

引用

DISCRETE MATHEMATICS 2022年第3期345卷 112733-112733页

作者： Pan, Zhishi Zhu, Xuding Tamkang Univ Dept Math New Taipei Taiwan Zhejiang Normal Univ Dept Math Jinhua Zhejiang Peoples R China

It is known that any signed series-parallel graph (G, sigma) has circular chromatic number at most 10/3. This paper proves that for each rational r is an element of [2,10/3], there is a signed series-parallel graph (G... 详细信息

关键词： Circular chromatic number Signed graph series-parallel graph

来源：评论

学校读者我要写书评

暂无评论

LINEAR-TIME COMPUTABILITY OF COMBINATORIAL PROBLEMS ON series-parallel graphS

引用

JOURNAL OF THE ACM 1982年第3期29卷 623-641页

作者： TAKAMIZAWA, K NISHIZEKI, T SAITO, N TOHOKU UNIV DEPT ELECT ENGN SENDAI MIYAGI 980 JAPAN

A series-parallel graph can be constructed from a certain graph by recurslvely applying “series” and “parallel” connections The class of such graphs, which Is a well-known model of series-parallel electrical networks, is a subclass of planar graphs It is shown in a umfied manner that there exist hnearume algorithms for many combinatorial problems ff an input graph is restricted to the class of series-parallel graphs. These include 0) the decision problem with respect to a property characterized by a finite number of forbidden graphs, (u) the mlmmum edge (vertex) deletion problem with respect to the same property as above, and (Ul) the generalized matching problem Consequently, the following problems, among others, prove to be hnear-tlme computable for the class of series-parallel graphs. (I) the minimum vertex cover problem, (2) the maximum outerplanar (reduced) subgraph problem, (3) the minimum feedback vertex set problem, (4) the maximum (induced) hne-subgraph problem, (5) the maximum matching problem, and (6) the maximum disjoint triangle problem. © 1982, ACM. All rights reserved.

关键词： Edge-deletion problem forbidden graph generahzed matching problem series-parallel graph vertex-deleuon problem

来源：评论

学校读者我要写书评

暂无评论

The strong fractional choice number of series-parallel graphs

引用

DISCRETE MATHEMATICS 2020年第5期343卷 111796-000页

作者： Li, Xuer Zhu, Xuding Zhejiang Normal Univ Dept Math Jinhua Zhejiang Peoples R China

The strong fractional choice number of a graph G is the infimum of those real numbers r such that G is (inverter right perpendicular rm inverter left perpendicular, m)-choosable for every positive integer m. The strong fractional choice number of a family G of graphs is the supremum of the strong fractional choice number of graphs in G. We denote by Q(k) the class of series-parallel graphs with girth at least k. This paper proves that the strong fractional choice number of Q(k) equals 2 + 1/ left perpendicular(k+1)/4 right perpendicular. (C) 2019 Published by Elsevier B.V.

关键词： Strong fractional choice number series-parallel graph Girth

来源：评论

学校读者我要写书评

暂无评论

Spanning Distribution Trees of graphs

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2014年第3期E97D卷 406-412页

作者： Kawabata, Masaki Nishizeki, Takao Kwansei Gakuin Univ Sch Sci & Technol Sanda 6691337 Japan

Let G be a graph with a single source w, assigned a positive integer called the supply. Every vertex other than w is a sink, assigned a nonnegative integer called the demand. Every edge is assigned a positive integer called the capacity. Then a spanning tree T of G is called a spanning distribution tree if the capacity constraint holds when, for every sink v, an amount of flow, equal to the demand of v, is sent from w to v along the path in T between them. The spanning distribution tree problem asks whether a given graph has a spanning distribution tree or not. In the paper, we first observe that the problem is NP-complete even for series-parallel graphs, and then give a pseudo-polynomial time algorithm to solve the problem for a given series-parallel graph G. The computation time is bounded by a polynomial in n and D, where n is the number of vertices in G and D is the sum of all demands in G.

关键词： spanning distribution tree series-parallel graph flow supply demand partial k-tree

来源：评论

学校读者我要写书评

暂无评论

Single machine scheduling with decreasing linear deterioration under precedence constraints

引用

COMPUTERS & MATHEMATICS WITH APPLICATIONS 2009年第1期58卷 95-103页

作者： Wang, Ji-Bo Shenyang Inst Aeronaut Engn Sch Sci Shenyang 110136 Peoples R China

This paper deals with single-machine scheduling problems with decreasing linear deterioration, i.e., jobs whose processing times are a decreasing function of their starting times. In addition, the jobs are related by parallel chains and a series-parallel graph precedence constraints, respectively. It is shown that for the problems of minimization of the makespan, polynomial algorithms exist. (C) 2009 Elsevier Ltd. All rights reserved.

关键词： Scheduling Single machine Deteriorating jobs parallel chains series-parallel graph Makespan

来源：评论

学校读者我要写书评

暂无评论

Box-total dual integrality and edge-connectivity

引用

MATHEMATICAL PROGRAMMING 2023年第1期197卷 307-336页

作者： Barbato, Michele Grappe, Roland Lacroix, Mathieu Lancini, Emiliano Univ Milan Dept Comp Sci I-20133 Milan Italy Univ Sorbonne Paris Nord LIPN CNRS UMR 7030 F-93430 Villetaneuse France Eseo F-78140 Velizy Villacoublay France

Given a graph G = (V, E) and an integer k >= 1, the graph H = (V, F), where F is a family of elements (with repetitions allowed) of E, is a k-edge-connected spanning subgraph of G if H cannot be disconnected by deleting any k - 1 elements of F. The convex hull of incidence vectors of the k-edge-connected subgraphs of a graph G forms the k-edge-connected subgraph polyhedron of G. We prove that this polyhedron is box-totally dual integral if and only if G is series-parallel. In this case, we also provide an integer box-totally dual integral system describing this polyhedron.

关键词： Box-total dual integrality k-edge connected subgraph Polyhedron series-parallel graph

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：