The Experts below are selected from a list of 327 Experts worldwide ranked by ideXlab platform
Toshihide Ibaraki - One of the best experts on this subject based on the ideXlab platform.
-
augmenting a k 1 vertex connected Multigraph l edge connected and k vertex connected Multigraph
Algorithmica, 2006Co-Authors: Toshimasa Ishii, Hiroshi Nagamochi, Toshihide IbarakiAbstract:For two integers $k,\ell > 0$ and an undirected Multigraph $G=(V,E)$, we consider the problem of augmenting $G$ by the smallest number of new edges to obtain an $\ell$-edge-connected and $k$-vertex-connected Multigraph. In this paper we show that a $(k-1)$-vertex-connected Multigraph $G$ can be made $\ell$-edge-connected and $k$-vertex-connected by adding at most $\bound$ surplus edges over the optimum in $O(\tm)$ time, where $n=|V|$.
-
Augmenting a (k - 1)-Vertex-Connected Multigraph ℓ-Edge-Connected and k-Vertex-Connected Multigraph
Algorithmica, 2005Co-Authors: Toshimasa Ishii, Hiroshi Nagamochi, Toshihide IbarakiAbstract:For two integers $k,\ell > 0$ and an undirected Multigraph $G=(V,E)$, we consider the problem of augmenting $G$ by the smallest number of new edges to obtain an $\ell$-edge-connected and $k$-vertex-connected Multigraph. In this paper we show that a $(k-1)$-vertex-connected Multigraph $G$ can be made $\ell$-edge-connected and $k$-vertex-connected by adding at most $\bound$ surplus edges over the optimum in $O(\tm)$ time, where $n=|V|$.
-
optimal augmentation of a 2 vertex connected Multigraph to a k edge connected and 3 vertex connected Multigraph
Journal of Combinatorial Optimization, 2000Co-Authors: Toshimasa Ishii, Hiroshi Nagamochi, Toshihide IbarakiAbstract:Given an undirected Multigraph G = (V, E) and two positive integers l and k, we consider the problem of augmenting G by the smallest number of new edges to obtain an l-edge-connected and k-vertex-connected Multigraph. In this paper, we show that the problem can be solved in O(mn2) time for any fixed l and k = 3 if an input Multigraph G is 2-vertex-connected, where n = |V| and m is the number of pairs of adjacent vertices in G.
-
augmenting a k 1 vertex connectedMultigraph to an l edge connected and k vertex connected Multigraph
European Symposium on Algorithms, 1999Co-Authors: Toshimasa Ishii, Hiroshi Nagamochi, Toshihide IbarakiAbstract:Given an undirected Multigraph G = (V,E) and two positive integers l and k, we consider the problem of augmenting G by the smallest number of new edges to obtain an l-edge-connected and k-vertex-connected Multigraph. In this paper, we show that an (k - 1)-vertex-connected Multigraph G (k ≥ 4) can be made l-edge-connected and k-vertex-connected by adding at most 2l surplus edges over the optimum, in \( O(\min \left\{ {k,\sqrt n \} kn^3 + n^4 } \right\}\) time, where n = |V|.
-
k edge and 3 vertex connectivity augmentation in an arbitrary Multigraph
International Symposium on Algorithms and Computation, 1998Co-Authors: Toshimasa Ishii, Hiroshi Nagamochi, Toshihide IbarakiAbstract:Given an undirected Multigraph G = (V,E) and two positive integers l and k, the edge-and-vertex connectivity augmentation problem asks to augment G by the smallest number of new edges so that the resulting Multigraph becomes l-edge-connected and k-vertex-connected. In this paper, we show that the problem with a fixed l and k = 3 can be solved in polynomial time for an arbitrary Multigraph G.
Toshimasa Ishii - One of the best experts on this subject based on the ideXlab platform.
-
augmenting a k 1 vertex connected Multigraph l edge connected and k vertex connected Multigraph
Algorithmica, 2006Co-Authors: Toshimasa Ishii, Hiroshi Nagamochi, Toshihide IbarakiAbstract:For two integers $k,\ell > 0$ and an undirected Multigraph $G=(V,E)$, we consider the problem of augmenting $G$ by the smallest number of new edges to obtain an $\ell$-edge-connected and $k$-vertex-connected Multigraph. In this paper we show that a $(k-1)$-vertex-connected Multigraph $G$ can be made $\ell$-edge-connected and $k$-vertex-connected by adding at most $\bound$ surplus edges over the optimum in $O(\tm)$ time, where $n=|V|$.
-
Augmenting a (k - 1)-Vertex-Connected Multigraph ℓ-Edge-Connected and k-Vertex-Connected Multigraph
Algorithmica, 2005Co-Authors: Toshimasa Ishii, Hiroshi Nagamochi, Toshihide IbarakiAbstract:For two integers $k,\ell > 0$ and an undirected Multigraph $G=(V,E)$, we consider the problem of augmenting $G$ by the smallest number of new edges to obtain an $\ell$-edge-connected and $k$-vertex-connected Multigraph. In this paper we show that a $(k-1)$-vertex-connected Multigraph $G$ can be made $\ell$-edge-connected and $k$-vertex-connected by adding at most $\bound$ surplus edges over the optimum in $O(\tm)$ time, where $n=|V|$.
-
optimal augmentation of a 2 vertex connected Multigraph to a k edge connected and 3 vertex connected Multigraph
Journal of Combinatorial Optimization, 2000Co-Authors: Toshimasa Ishii, Hiroshi Nagamochi, Toshihide IbarakiAbstract:Given an undirected Multigraph G = (V, E) and two positive integers l and k, we consider the problem of augmenting G by the smallest number of new edges to obtain an l-edge-connected and k-vertex-connected Multigraph. In this paper, we show that the problem can be solved in O(mn2) time for any fixed l and k = 3 if an input Multigraph G is 2-vertex-connected, where n = |V| and m is the number of pairs of adjacent vertices in G.
-
augmenting a k 1 vertex connectedMultigraph to an l edge connected and k vertex connected Multigraph
European Symposium on Algorithms, 1999Co-Authors: Toshimasa Ishii, Hiroshi Nagamochi, Toshihide IbarakiAbstract:Given an undirected Multigraph G = (V,E) and two positive integers l and k, we consider the problem of augmenting G by the smallest number of new edges to obtain an l-edge-connected and k-vertex-connected Multigraph. In this paper, we show that an (k - 1)-vertex-connected Multigraph G (k ≥ 4) can be made l-edge-connected and k-vertex-connected by adding at most 2l surplus edges over the optimum, in \( O(\min \left\{ {k,\sqrt n \} kn^3 + n^4 } \right\}\) time, where n = |V|.
-
k edge and 3 vertex connectivity augmentation in an arbitrary Multigraph
International Symposium on Algorithms and Computation, 1998Co-Authors: Toshimasa Ishii, Hiroshi Nagamochi, Toshihide IbarakiAbstract:Given an undirected Multigraph G = (V,E) and two positive integers l and k, the edge-and-vertex connectivity augmentation problem asks to augment G by the smallest number of new edges so that the resulting Multigraph becomes l-edge-connected and k-vertex-connected. In this paper, we show that the problem with a fixed l and k = 3 can be solved in polynomial time for an arbitrary Multigraph G.
Hiroshi Nagamochi - One of the best experts on this subject based on the ideXlab platform.
-
augmenting a k 1 vertex connected Multigraph l edge connected and k vertex connected Multigraph
Algorithmica, 2006Co-Authors: Toshimasa Ishii, Hiroshi Nagamochi, Toshihide IbarakiAbstract:For two integers $k,\ell > 0$ and an undirected Multigraph $G=(V,E)$, we consider the problem of augmenting $G$ by the smallest number of new edges to obtain an $\ell$-edge-connected and $k$-vertex-connected Multigraph. In this paper we show that a $(k-1)$-vertex-connected Multigraph $G$ can be made $\ell$-edge-connected and $k$-vertex-connected by adding at most $\bound$ surplus edges over the optimum in $O(\tm)$ time, where $n=|V|$.
-
Augmenting a (k - 1)-Vertex-Connected Multigraph ℓ-Edge-Connected and k-Vertex-Connected Multigraph
Algorithmica, 2005Co-Authors: Toshimasa Ishii, Hiroshi Nagamochi, Toshihide IbarakiAbstract:For two integers $k,\ell > 0$ and an undirected Multigraph $G=(V,E)$, we consider the problem of augmenting $G$ by the smallest number of new edges to obtain an $\ell$-edge-connected and $k$-vertex-connected Multigraph. In this paper we show that a $(k-1)$-vertex-connected Multigraph $G$ can be made $\ell$-edge-connected and $k$-vertex-connected by adding at most $\bound$ surplus edges over the optimum in $O(\tm)$ time, where $n=|V|$.
-
optimal augmentation of a 2 vertex connected Multigraph to a k edge connected and 3 vertex connected Multigraph
Journal of Combinatorial Optimization, 2000Co-Authors: Toshimasa Ishii, Hiroshi Nagamochi, Toshihide IbarakiAbstract:Given an undirected Multigraph G = (V, E) and two positive integers l and k, we consider the problem of augmenting G by the smallest number of new edges to obtain an l-edge-connected and k-vertex-connected Multigraph. In this paper, we show that the problem can be solved in O(mn2) time for any fixed l and k = 3 if an input Multigraph G is 2-vertex-connected, where n = |V| and m is the number of pairs of adjacent vertices in G.
-
augmenting a k 1 vertex connectedMultigraph to an l edge connected and k vertex connected Multigraph
European Symposium on Algorithms, 1999Co-Authors: Toshimasa Ishii, Hiroshi Nagamochi, Toshihide IbarakiAbstract:Given an undirected Multigraph G = (V,E) and two positive integers l and k, we consider the problem of augmenting G by the smallest number of new edges to obtain an l-edge-connected and k-vertex-connected Multigraph. In this paper, we show that an (k - 1)-vertex-connected Multigraph G (k ≥ 4) can be made l-edge-connected and k-vertex-connected by adding at most 2l surplus edges over the optimum, in \( O(\min \left\{ {k,\sqrt n \} kn^3 + n^4 } \right\}\) time, where n = |V|.
-
k edge and 3 vertex connectivity augmentation in an arbitrary Multigraph
International Symposium on Algorithms and Computation, 1998Co-Authors: Toshimasa Ishii, Hiroshi Nagamochi, Toshihide IbarakiAbstract:Given an undirected Multigraph G = (V,E) and two positive integers l and k, the edge-and-vertex connectivity augmentation problem asks to augment G by the smallest number of new edges so that the resulting Multigraph becomes l-edge-connected and k-vertex-connected. In this paper, we show that the problem with a fixed l and k = 3 can be solved in polynomial time for an arbitrary Multigraph G.
Harold N Gabow - One of the best experts on this subject based on the ideXlab platform.
-
an improved analysis for approximating the smallest k edge connected spanning subgraph of a Multigraph
SIAM Journal on Discrete Mathematics, 2005Co-Authors: Harold N GabowAbstract:Khuller and Raghavachari [J. Algorithms, 21 (1996), pp. 434--450] present an approximation algorithm (the KR algorithm) for finding the smallest k-edge connected spanning subgraph (k-ECSS) of an undirected Multigraph. They prove the KR algorithm has an approximation ratio < 1.85. We improve this bound to $\le 1+\sqrt{1/e}<1.61$ (for odd k we modify the base case of the KR algorithm). This is the best-known performance bound for a combinatorial approximation algorithm for the smallest k-ECSS problem for arbitrary k. Our analysis also gives the best-known combinatorial performance bound for any fixed value of $k\ge 3$, e.g., for even k the approximation ratio is $\le 1+(1-{1\over k})^{k/2}$. Our analysis is based on a laminar family of sets (similar to families used in related contexts) which gives a better accounting of edges added in previous iterations of the algorithm. We also present a polynomial time implementation of the KR algorithm on Multigraphs, running in the time for O(nm) maximum flow computations, where n (m) is the number of vertices (edges, not counting parallel copies), respectively. This complements the implementation of Khuller and Raghavachari [J. Algorithms, 21 (1996), pp. 434--450] which uses time O((kn)2) and is efficient for small k.
-
better performance bounds for finding the smallest k edge connected spanning subgraph of a Multigraph
Symposium on Discrete Algorithms, 2003Co-Authors: Harold N GabowAbstract:Khuller and Raghavachari [12] present an approximation algorithm (the KR algorithm) for finding the smallest k-edge connected spanning subgraph (k-ECSS) of an undirected Multigraph. They prove the KR algorithm has approximation ratio < 1.85. We prove the KR algorithm has approximation ratio ≤ 1 + √1/e < 1.61; for odd k this requires a minor modification of the algorithm. This is the bestknown performance bound for the smallest k-ECSS problem for arbitrary k. Our analysis also gives the best-known performance bound for any fixed value of k ≤ 3, e.g., for even k the approximation ratio is ≤ 1 + (1 -- 1/k)k/2. Our analysis is based on a laminar family of sets (similar to families used in related contexts) which gives a better accounting of edges added in previous iterations of the algorithm. We also present a polynomial time implementation of the KR algorithm on Multigraphs, running in the time for O(nm) maximum flow computations, where n (m) is the number of vertices (edges, not counting parallel copies). This complements the implementation of [12] which uses time O((kn)2) and is efficient for small k.
Pascal Poncelet - One of the best experts on this subject based on the ideXlab platform.
-
Mining Frequent Subgraphs in Multigraphs
Information Sciences, 2018Co-Authors: Vijay Ingalalli, Dino Ienco, Pascal PonceletAbstract:For more than a decade, extracting frequent patterns from single large graphs has been one of the research focuses. However, in this era of data eruption, rich and complex data is being generated at an unprecedented rate. This complex data can be represented as a Multigraph structure-a generic and rich graph representation. In this paper, we propose a novel frequent subgraph mining approach MuGraM that can be applied to Multigraphs. MuGraM is a generic frequent subgraph mining algorithm that discovers frequent Multigraph patterns. MuGraM eciently performs the task of subgraph matching, which is crucial for support measure, and further leverages several optimization techniques for swift discovery of frequent subgraphs. Our experiments reveal two things: MuGraM discovers Multigraph patterns, where other existing approaches are unable to do so; MuGraM, when applied to simple graphs, outperforms the state of the art approaches by at least one order of magnitude.
-
Querying RDF Data: A Multigraph Based Approach
2018Co-Authors: Vijay Ingalalli, Dino Ienco, Pascal PonceletAbstract:Resource description framework (RDF) data are cherished and exploited by various domains such as life sciences, Semantic Web and social networks. This chapter provides basic definitions on the interplay between RDF and its Multigraph representation. The Multigraph representation enables to construct lightweight indexing structures that ameliorate the time performance of Attributed Multigraph Based Engine for RDF querying (AMbER). The chapter discusses a graph‐based RDF querying engine, AMbER, which involves two steps. The first step is an offline step, where RDF data are transformed into Multigraph and are indexed. The second step is an online step, where an efficient approach to answer a SPARQL query is proposed. The proposed engine AMbER has been tested over large RDF triplestores. The chapter focuses on the SELECT/WHERE clause of the SPARQL language, which constitutes the most important operation of any RDF query engine.
-
querying rdf data using a Multigraph based approach
Extending Database Technology, 2016Co-Authors: Vijay Ingalalli, Dino Ienco, Pascal Poncelet, Serena VillataAbstract:RDF is a standard for the conceptual description of knowledge , and SPARQL is the query language conceived to query RDF data. The RDF data is cherished and exploited by various domains such as life sciences, Semantic Web, social network, etc. Further, its integration at Web-scale compels RDF management engines to deal with complex queries in terms of both size and structure. In this paper, we propose AMbER (Attributed Multigraph Based Engine for RDF querying), a novel RDF query engine specifically designed to optimize the computation of complex queries. AMbER leverages subgraph matching techniques and extends them to tackle the SPARQL query problem. First of all RDF data is represented as a Multigraph, and then novel indexing structures are established to efficiently access the information from the Multigraph. Finally a SPARQL query is represented as a Multigraph, and the SPARQL querying problem is reduced to the subgraph homomorphism problem. AMbER exploits structural properties of the query Multigraph as well as the proposed indexes, in order to tackle the problem of subgraph homomorphism. The performance of AMbER, in comparison with state-of-the-art systems, has been extensively evaluated over several RDF benchmarks. The advantages of employing AMbER for complex SPARQL queries have been experimentally validated.
-
Layer-Centered Approach for Multigraphs Visualization
2015 19th International Conference on Information Visualisation, 2015Co-Authors: Denis Redondo, Dino Ienco, Arnaud Sallaberry, Faraz Zaidi, Pascal PonceletAbstract:Recent advances in network science allows the modeling and analysis of complex inter-related entities. These entities often interact with each other in a number of different ways. Simple graphs fail to capture these multiple types of relationships requiring more sophisticated mathematical structures. One such structure is Multigraph, where entities (or nodes) can be linked to each other through multiple edges. In this paper we describe a new method to manage multiple types of relationships existing in Multigraphs. Our approach is based on the concept of pair of nodes (edges) and, in particular, we study how nodes on different layers interact which each other considering the edges they share. We propose a two level strategy that summarizes global/local Multigraph features. The global view helps us to gain knowledge related to the characteristics of layers and how they interact while the local view provides an analysis of individual layers highlighting edge properties such as cluster structure. Our proposal is complementary to standard node-link diagram and it can be coupled with such techniques in order to intelligently explore Multigraphs. The proposed visualization is tested on a real world case study and the outcomes point out the ability of our proposal to discover patterns present in the data.
