One of the most noted construction methods of 3-vertex-connected graphs is due to Tutte and is based on the following fact: Any 3-vertex-connected graph G = (V, E) on more than 4 vertices contains a contractible edge,...
详细信息
One of the most noted construction methods of 3-vertex-connected graphs is due to Tutte and is based on the following fact: Any 3-vertex-connected graph G = (V, E) on more than 4 vertices contains a contractible edge, i.e., an edge whose contraction generates a 3-connected graph. This implies the existence of a sequence of edge contractions from G to the complete graph K-4, such that every intermediate graph is 3-vertex-connected. A theorem of Barnette and Grunbaum gives a similar sequence using removals on edges instead of contractions. We show how to compute both sequences in optimal time, improving the previously best known running times of O(vertical bar V vertical bar(2)) to O(vertical bar E vertical bar). This result has a number of consequences;an important one is a new linear-time test of 3-connectivity that is certifying;finding such an algorithm has been a major open problem in the design of certifying algorithms in recent years. The test is conceptually different from well-known linear-time 3-connectivity tests and uses a certificate that is easy to verify in time O(vertical bar E vertical bar). We show how to extend the results to an optimal certifying test of 3-edge-connectivity.
We present a certifying algorithm that tests graphs for 3-edge-connectivity;the algorithm works in linear time. If the input graph is not 3-edge-connected, the algorithm returns a 2-edge-cut. If it is 3-edge-connected...
详细信息
We present a certifying algorithm that tests graphs for 3-edge-connectivity;the algorithm works in linear time. If the input graph is not 3-edge-connected, the algorithm returns a 2-edge-cut. If it is 3-edge-connected, it returns a construction sequence that constructs the input graph from the graph with two vertices and three parallel edges using only operations that (obviously) preserve 3-edge-connectivity. Additionally, we show how to compute and certify the 3-edge-connected components and a cactus representation of the 2-cuts in linear time. For 3-vertex-connectivity, we show how to compute the 3-vertex-connected components of a 2-connected graph.
Tutte proved that every 3-vertex-connected graph G on more than 4 vertices has a contractible edge. Barnette and Grunbaum proved the existence of a removable edge in the same setting. We show that the sequence of cont...
详细信息
Tutte proved that every 3-vertex-connected graph G on more than 4 vertices has a contractible edge. Barnette and Grunbaum proved the existence of a removable edge in the same setting. We show that the sequence of contractions and the sequence of removals from G to K (4) can be computed in O(|V|(2)) time by extending Barnette's and Grunbaum's theorem. As an application, we derive a certificate for the 3-vertex-connectivity of graphs that can be easily computed and verified.
We introduce I/O-effiient certifying algorithms for bipartite graphs, as well as for the classes of split, threshold, bipartite chain, and trivially perfect graphs. When the input graph is a member of the respective c...
详细信息
ISBN:
(纸本)9783031270505;9783031270512
We introduce I/O-effiient certifying algorithms for bipartite graphs, as well as for the classes of split, threshold, bipartite chain, and trivially perfect graphs. When the input graph is a member of the respective class, the certifying algorithm returns a certificate that characterizes this class. Otherwise, it returns a forbidden induced subgraph as a certificate for non-membership. On a graph with n vertices and m edges, our algorithms take O(SORT(n + m)) I/Os in the worst case for split, threshold and trivially perfect graphs. In the same complexity bipartite and bipartite chain graphs can be certified with high probability. We provide implementations for split and threshold graphs and provide a preliminary experimental evaluation.
Tutte proved that every 3-connected graph on more than 4 nodes has a contractible edge. Barnette and Grunbaum proved the existence of a removable edge in the same setting. We show that the sequence of contractions and...
详细信息
ISBN:
(纸本)9783939897163
Tutte proved that every 3-connected graph on more than 4 nodes has a contractible edge. Barnette and Grunbaum proved the existence of a removable edge in the same setting. We show that the sequence of contractions and the sequence of removals from C to the K-4 can be computed in O(|V|(2)) time by extending Barnette and Grunbaum's theorem. As an application, we derive a certificate for the 3-connectedness of graphs that can be easily computed and verified.
A bipartite graph G = (U, V, E) is convex if the vertices in V can be linearly ordered such that for each vertex u is an element of U, the neighbors of u are consecutive in the ordering of V. An induced matching H of ...
详细信息
A bipartite graph G = (U, V, E) is convex if the vertices in V can be linearly ordered such that for each vertex u is an element of U, the neighbors of u are consecutive in the ordering of V. An induced matching H of G is amatching for which no edge of E connects endpoints of two different edges of H. We show that in a convex bipartite graph with n vertices and m weighted edges, an induced matching of maximum total weight can be computed in O(n + m) time. An unweighted convex bipartite graph has a representation of size O(n) that records for each vertex u is an element of U the first and last neighbor in the ordering of V. Given such a compact representation, we compute an induced matching of maximum cardinality in O(n) time. In convex bipartite graphs, maximum-cardinality induced matchings are dual to minimum chain covers. A chain cover is a covering of the edge set by chain subgraphs, that is, subgraphs that do not contain induced matchings of more than one edge. Given a compact representation, we compute a representation of a minimum chain cover in O(n) time. If no compact representation is given, the cover can be computed in O(n+ m) time. All of our algorithms achieve optimal linear running time for the respective problem and model, and they improve and generalize the previous results in several ways: The best algorithms for the unweighted problem versions had a running time of O(n(2)) (Brandstadt et al. in Theor. Comput. Sci. 381(1-3):260-265, 2007. https://***/10.1016/***.2007.04.006). The weighted case has not been considered before.
We present an algorithm to color a graph G with no triangle and no induced 7-vertex path (i.e., a {P-7, C-3}-free graph), where every vertex is assigned a list of possible colors which is a subset of {1, 2, 3}. While ...
详细信息
We present an algorithm to color a graph G with no triangle and no induced 7-vertex path (i.e., a {P-7, C-3}-free graph), where every vertex is assigned a list of possible colors which is a subset of {1, 2, 3}. While this is a special case of the problem solved in Bonomo et al. (2018) [1], that does not require the absence of triangles, the algorithm here is both faster and conceptually simpler. The complexity of the algorithm is O(vertical bar V (G)vertical bar(5)(vertical bar V (G)vertical bar + vertical bar E(G)vertical bar)), and if G is bipartite, it improves to O(vertical bar V (G)vertical bar(2)(vertical bar V (G)vertical bar + vertical bar E(G)vertical bar)). Moreover, we prove that there are finitely many minimal obstructions to list 3-coloring {P-t, C-3}-free graphs if and only if t <= 7. This implies the existence of a polynomial time certifying algorithm for list 3-coloring in {P-7, C-3}-free graphs. We furthermore determine other cases of t, l, and k such that the family of minimal obstructions to list k-coloring in {P-t, C-l}-free graphs is finite. (C) 2020 Elsevier B.V. All rights reserved.
We consider the problem of computing k is an element of N internally vertex-disjoint paths between special vertex pairs of simple connected graphs. For general vertex pairs, the best deterministic time bound is, since...
详细信息
We consider the problem of computing k is an element of N internally vertex-disjoint paths between special vertex pairs of simple connected graphs. For general vertex pairs, the best deterministic time bound is, since 42 years, O(min{k,n}m) for each pair by using traditional flow-based methods. The restriction of our vertex pairs comes from the machinery of maximal adjacency orderings (MAOs). Henzinger showed for every MAO and every 1 <= k <=delta (where delta is the minimum degree of the graph) the existence of k internally vertex-disjoint paths between every pair of the last delta-k+2 vertices of this MAO. Later, Nagamochi generalized this result by using the machinery of mixed connectivity. Both results are however inherently non-constructive. We present the first algorithm that computes these k internally vertex-disjoint paths in linear time O(n+m), which improves the previously best time O(min{k,n}m). Due to the linear running time, this algorithm is suitable for large graphs. The algorithm is simple, works directly on the MAO structure, and completes a long history of purely existential proofs with a constructive method. We extend our algorithm to compute several other path systems and discuss its impact for certifying algorithms.
Given a graph G and integers k(1), k(2), and k(3), the unit interval editing problem asks whether G can be transformed into a unit interval graph by at most k(1) vertex deletions, k(2) edge deletions, and k(3) edge ad...
详细信息
Given a graph G and integers k(1), k(2), and k(3), the unit interval editing problem asks whether G can be transformed into a unit interval graph by at most k(1) vertex deletions, k(2) edge deletions, and k(3) edge additions. We give an algorithm solving this problem in time 2(o(klogk)). (n+m), where k := k(1) + k(2) + k(3), and n,m denote respectively the numbers of vertices and edges of G. Therefore, it is fixed-parameter tractable parameterized by the total number of allowed operations. Our algorithm implies the fixed -parameter tractability of the unit interval edge deletion problem, for which we also present a more efficient algorithm running in time O(4(k) (n +m)). Another result is an 0 (6(k) . (n +m))-time algorithm for the unit interval vertex deletion problem, significantly improving the algorithm of van 't Hof and Villanger, which runs in time O(6(k) .n(6)). (C) 2017 Elsevier Inc. All rights reserved.
A binary matrix has the Consecutive Ones Property (C1P) if it is possible to order the columns so that all Is are consecutive in every row. In [McConnell, SODA 2004, pp. 768-777] the notion of incompatibility graph of...
详细信息
A binary matrix has the Consecutive Ones Property (C1P) if it is possible to order the columns so that all Is are consecutive in every row. In [McConnell, SODA 2004, pp. 768-777] the notion of incompatibility graph of a binary matrix was introduced and it was shown that odd cycles of this graph provide a certificate that a matrix does not have the Consecutive Ones Property. A bound of k + 2 was claimed for the smallest odd cycle of a non-C1P matrix with k columns. In this Note we show that this result can be obtained simply and directly via Tucker patterns, and that the correct bound is k + 2 when k is even, but k + 3 when k is odd. (c) 2012 Elsevier B.V. All rights reserved.
暂无评论