The Experts below are selected from a list of 297 Experts worldwide ranked by ideXlab platform
Sébastien Martin - One of the best experts on this subject based on the ideXlab platform.
-
The multi-Terminal Vertex separator problem: Branch-and-Cut-and-Price
Discrete Applied Mathematics, 2021Co-Authors: Youcef Magnouche, Ali Ridha Mahjoub, Sébastien MartinAbstract:Abstract We are given a graph G = ( V ∪ T , E ) , with V ∪ T the set of vertices where T is a set of Terminals and E the set of edges. The multi-Terminal Vertex separator problem consists in finding a subset of vertices S ⊆ V of minimum size intersecting all paths between every pair of Terminals. In this paper we present three extended linear integer programming formulations for the multi-Terminal Vertex separator problem and we develop Branch-and-Price and Branch-and-Cut-and-Price algorithms. For each formulation we present the pricing problem, the branching scheme and the computation of the dual bound used during the column generation phase. Computational results are reported comparing the performance of the formulations on a set of instances.
-
the multi Terminal Vertex separator problem polyhedral analysis and branch and cut
Discrete Applied Mathematics, 2019Co-Authors: Denis Cornaz, Youcef Magnouche, Ali Ridha Mahjoub, Sébastien MartinAbstract:In this paper we consider a variant of the k-separator problem. Given a graph G=(V∪T,E) with V∪T the set of vertices, where T is a set of k Terminals, the multi-Terminal Vertex separator problem consists in partitioning V∪T into k+1 subsets {S,V1,...,Vk} such that there is no edge between two different subsets Vi and Vj, each Vi contains exactly one Terminal and the size of S is minimum. In this paper, we first show that the problem is NP-hard. Then we give two integer programming formulations for the problem. For one of these formulations, we investigate the related polyhedron and discuss its polyhedral structure. We describe some valid inequalities and characterize when these inequalities define facets. We also derive separation algorithms for these inequalities. Using these results, we develop a Branch-and-Cut algorithm for the problem, along with an extensive computational study.
-
ISCO - The Multi-Terminal Vertex Separator Problem: Polytope Characterization and TDI-ness
Lecture Notes in Computer Science, 2016Co-Authors: Youcef Magnouche, Sébastien MartinAbstract:In this paper we discuss a variant of the well-known k-separator problem. Consider the simple graph \(G=(V\cup T,E)\) with \(V\cup T\) the set of vertices, where T is a set of distinguished vertices called Terminals, inducing a stable set and E a set of edges. Given a weight function \(w: V\rightarrow \mathbb N\), the multi-Terminal Vertex separator problem consists in finding a subset \(S\subseteq V\) of minimum weight intersecting every path between two Terminals. We characterize the convex hull of the solutions of this problem in two classes of graph which we call, star trees and clique stars. We also give TDI systems for the problem in these graphs.
-
the multi Terminal Vertex separator problem polytope characterization and tdi ness
International Symposium on Combinatorial Optimization, 2016Co-Authors: Youcef Magnouche, Sébastien MartinAbstract:In this paper we discuss a variant of the well-known k-separator problem. Consider the simple graph \(G=(V\cup T,E)\) with \(V\cup T\) the set of vertices, where T is a set of distinguished vertices called Terminals, inducing a stable set and E a set of edges. Given a weight function \(w: V\rightarrow \mathbb N\), the multi-Terminal Vertex separator problem consists in finding a subset \(S\subseteq V\) of minimum weight intersecting every path between two Terminals. We characterize the convex hull of the solutions of this problem in two classes of graph which we call, star trees and clique stars. We also give TDI systems for the problem in these graphs.
-
the multi Terminal Vertex separator problem extended formulations and branch and cut and price
International Conference on Control Decision and Information Technologies, 2016Co-Authors: Youcef Magnouche, Ridha A Mahjoub, Sébastien MartinAbstract:In this paper we discuss a variant of the well-known k-separator problem. Given a simple graph G = (V ∪ T, E) with V ∪ T the set of vertices, where T is a set of distinguished vertices called Terminals, and E a set of edges, the multi-Terminal Vertex separator problem consists in partitioning V ∪T into k+1 subsets {S, V 1 , …, V k } such that the size of S is minimum, each subset V i contains exactly one Terminal and no Vertex in V i is adjacent to a Vertex in V j . Three extended formulations are proposed for the problem. We develop Branch-and-Price algorithms for the two first formulations and a Branch-and-Cut-and-Price algorithm for the third one. Some experimental results are also discussed.
Youcef Magnouche - One of the best experts on this subject based on the ideXlab platform.
-
The multi-Terminal Vertex separator problem: Branch-and-Cut-and-Price
Discrete Applied Mathematics, 2021Co-Authors: Youcef Magnouche, Ali Ridha Mahjoub, Sébastien MartinAbstract:Abstract We are given a graph G = ( V ∪ T , E ) , with V ∪ T the set of vertices where T is a set of Terminals and E the set of edges. The multi-Terminal Vertex separator problem consists in finding a subset of vertices S ⊆ V of minimum size intersecting all paths between every pair of Terminals. In this paper we present three extended linear integer programming formulations for the multi-Terminal Vertex separator problem and we develop Branch-and-Price and Branch-and-Cut-and-Price algorithms. For each formulation we present the pricing problem, the branching scheme and the computation of the dual bound used during the column generation phase. Computational results are reported comparing the performance of the formulations on a set of instances.
-
the multi Terminal Vertex separator problem polyhedral analysis and branch and cut
Discrete Applied Mathematics, 2019Co-Authors: Denis Cornaz, Youcef Magnouche, Ali Ridha Mahjoub, Sébastien MartinAbstract:In this paper we consider a variant of the k-separator problem. Given a graph G=(V∪T,E) with V∪T the set of vertices, where T is a set of k Terminals, the multi-Terminal Vertex separator problem consists in partitioning V∪T into k+1 subsets {S,V1,...,Vk} such that there is no edge between two different subsets Vi and Vj, each Vi contains exactly one Terminal and the size of S is minimum. In this paper, we first show that the problem is NP-hard. Then we give two integer programming formulations for the problem. For one of these formulations, we investigate the related polyhedron and discuss its polyhedral structure. We describe some valid inequalities and characterize when these inequalities define facets. We also derive separation algorithms for these inequalities. Using these results, we develop a Branch-and-Cut algorithm for the problem, along with an extensive computational study.
-
The multi-Terminal Vertex separator problem : Complexity, Polyhedra and Algorithms
2017Co-Authors: Youcef MagnoucheAbstract:Given a graph G = (V U T, E) with V U T the set of vertices, where T is a set of Terminals, and a weight function w, associated with the nonTerminal nodes, the multi-Terminal Vertex separator problem consists in partitioning V U T into k + 1 subsets {S, V1,..., Vk} such that there is no edge between two different subsets Vi and Vj, each Vi contains exactly one Terminal and the weight of S is minimum. In this thesis, we consider the problem from a polyhedral point of view. We give two integer programming formulations for the problem, for one of them, we investigate the related polyhedron. We describe some valid inequalities and characterize when these inequalities define facets. Using these results, we develop a Branch-and-Cut algorithm for the problem. We also study the multi-Terminal Vertex separator polytope in the graphs decomposable by one node cutsets. If G is a graph that decomposes into G1 and G2, we show that the multi-Terminal Vertex separator polytope in G can be described from two linear systems related to G1 and G2. This gives rise to a technique for characterizing the multi-Terminal Vertex separator polytope in the graphs that are recursively decomposable. Moreover, we propose three extended formulations for the problem and derive Branch-and-Price and Branch-and-Cut-and-Price algorithms. For each formulation we present a column generation scheme, the way to compute the dual bound, and the branching scheme. Finally, we discuss four variants of the multi-Terminal Vertex separator problem. We show that all these variants are NP-hard and for each one we give an integer programming formulation and present some class of valid inequalities.
-
ISCO - The Multi-Terminal Vertex Separator Problem: Polytope Characterization and TDI-ness
Lecture Notes in Computer Science, 2016Co-Authors: Youcef Magnouche, Sébastien MartinAbstract:In this paper we discuss a variant of the well-known k-separator problem. Consider the simple graph \(G=(V\cup T,E)\) with \(V\cup T\) the set of vertices, where T is a set of distinguished vertices called Terminals, inducing a stable set and E a set of edges. Given a weight function \(w: V\rightarrow \mathbb N\), the multi-Terminal Vertex separator problem consists in finding a subset \(S\subseteq V\) of minimum weight intersecting every path between two Terminals. We characterize the convex hull of the solutions of this problem in two classes of graph which we call, star trees and clique stars. We also give TDI systems for the problem in these graphs.
-
the multi Terminal Vertex separator problem polytope characterization and tdi ness
International Symposium on Combinatorial Optimization, 2016Co-Authors: Youcef Magnouche, Sébastien MartinAbstract:In this paper we discuss a variant of the well-known k-separator problem. Consider the simple graph \(G=(V\cup T,E)\) with \(V\cup T\) the set of vertices, where T is a set of distinguished vertices called Terminals, inducing a stable set and E a set of edges. Given a weight function \(w: V\rightarrow \mathbb N\), the multi-Terminal Vertex separator problem consists in finding a subset \(S\subseteq V\) of minimum weight intersecting every path between two Terminals. We characterize the convex hull of the solutions of this problem in two classes of graph which we call, star trees and clique stars. We also give TDI systems for the problem in these graphs.
Toshimasa Watanabe - One of the best experts on this subject based on the ideXlab platform.
-
extracting a planar spanning subgraph of a Terminal Vertex graph by solving the independent set problem
International Symposium on Circuits and Systems, 2001Co-Authors: T Yamaoki, Satoshi Taoka, Toshimasa WatanabeAbstract:This paper proposes four heuristic algorithms MISi (i=1,2,3,4) for extracting a spanning planar subgraph from a given Terminal-Vertex graph, in which a path or a directed cycle represents how pins of a given element of electrical circuits are located, and a net does connection requirement among pins. Extracting a largest possible planar spanning subgraph of a Terminal-Vertex graph has application to layout design of printed wiring boards or of VLSI. Experimental results show that all of the proposed algorithms outperform the existing one MNC, which has been showing the highest capability, and that MIS3 or MIS4 gives the best performance among them.
-
extracting nonplanar connections in a Terminal Vertex graph
International Symposium on Circuits and Systems, 1999Co-Authors: E Miuno, T Abaashi, Toshimasa WatanabeAbstract:This paper proposes a method for extracting a spanning planar subgraph from a given graph called a Terminal-Vertex graph, in which a path or a directed cycle represents how pins of a given element of electrical circuits are located, and a net performs the connection requirement among pins. It is based on transforming the graph without changing the connection requirement of each net. Experimental results are provided to show the capability of the proposed method. Finding a smallest possible set of nonplanar connections or extracting a largest planar spanning subgraph of this graph has application to the routing problem in layout design of printed wiring boards or of VLSI.
-
ISCAS (5) - Extracting a planar spanning subgraph of a Terminal-Vertex graph by solving the independent set problem
ISCAS 2001. The 2001 IEEE International Symposium on Circuits and Systems (Cat. No.01CH37196), 1Co-Authors: T Yamaoki, Satoshi Taoka, Toshimasa WatanabeAbstract:This paper proposes four heuristic algorithms MISi (i=1,2,3,4) for extracting a spanning planar subgraph from a given Terminal-Vertex graph, in which a path or a directed cycle represents how pins of a given element of electrical circuits are located, and a net does connection requirement among pins. Extracting a largest possible planar spanning subgraph of a Terminal-Vertex graph has application to layout design of printed wiring boards or of VLSI. Experimental results show that all of the proposed algorithms outperform the existing one MNC, which has been showing the highest capability, and that MIS3 or MIS4 gives the best performance among them.
-
ISCAS (6) - Extracting nonplanar connections in a Terminal-Vertex graph
ISCAS'99. Proceedings of the 1999 IEEE International Symposium on Circuits and Systems VLSI (Cat. No.99CH36349), 1Co-Authors: E Miuno, T Abaashi, Toshimasa WatanabeAbstract:This paper proposes a method for extracting a spanning planar subgraph from a given graph called a Terminal-Vertex graph, in which a path or a directed cycle represents how pins of a given element of electrical circuits are located, and a net performs the connection requirement among pins. It is based on transforming the graph without changing the connection requirement of each net. Experimental results are provided to show the capability of the proposed method. Finding a smallest possible set of nonplanar connections or extracting a largest planar spanning subgraph of this graph has application to the routing problem in layout design of printed wiring boards or of VLSI.
John D. Lagrange - One of the best experts on this subject based on the ideXlab platform.
-
The subgroup graph of a group
Arabian Journal of Mathematics, 2012Co-Authors: David F. Anderson, Jodi Fasteen, John D. LagrangeAbstract:Given any subgroup H of a group G , let Γ_ H ( G ) be the directed graph with Vertex set G such that x is the initial Vertex and y is the Terminal Vertex of an edge if and only if x ≠ y and $${xy\in H}$$ . Furthermore, if $${xy\in H}$$ and $${yx\in H}$$ for some $${x,y\in G}$$ with x ≠ y , then x and y will be regarded as being connected by a single undirected edge. In this paper, the structure of the connected components of Γ_ H ( G ) is investigated. All possible components are provided in the cases when | H | is either two or three, and the graph Γ_ H ( G ) is completely classified in the case when H is a normal subgroup of G and G / H is a finite abelian group.
-
The subgroup graph of a group
Arabian Journal of Mathematics, 2012Co-Authors: David F. Anderson, Jodi Fasteen, John D. LagrangeAbstract:Given any subgroup H of a group G, let Γ H (G) be the directed graph with Vertex set G such that x is the initial Vertex and y is the Terminal Vertex of an edge if and only if x ≠ y and \({xy\in H}\) . Furthermore, if \({xy\in H}\) and \({yx\in H}\) for some \({x,y\in G}\) with x ≠ y, then x and y will be regarded as being connected by a single undirected edge. In this paper, the structure of the connected components of Γ H (G) is investigated. All possible components are provided in the cases when |H| is either two or three, and the graph Γ H (G) is completely classified in the case when H is a normal subgroup of G and G/H is a finite abelian group. Open image in new window
Ke Wang - One of the best experts on this subject based on the ideXlab platform.
-
Development of alternative stochastic frontier models for estimating time-space prism vertices
Transportation, 2020Co-Authors: Ke WangAbstract:This paper develops alternative stochastic frontier models (ASFM) for estimating time-space prism vertices with different distributional assumptions for the inefficiency term that takes a non-negative value. The traditional stochastic frontier model (SFM) assumes that the inefficiency term follows a half-normal or exponential distribution. Under those assumptions, most travelers’ home departure/arrival time will be close to prism vertices, which is not necessarily consistent with actual travel behaviors. To avoid this potential problem, the ASFM adopt alternative distributions for the inefficiency term whose density values can decrease monotonously or vary non-monotonously. Quasi-Monte Carlo simulation method is employed to estimate the ASFM without closed-form likelihood expressions. Simulation experiment results show that SFM needs a substantially greater number of Halton draws for consistent estimators than a typical mixed logit model does. The ASFM are estimated based on the travel data of 1454 Shanghai commuters and 2964 Houston commuters. It is found that models with inefficiency term following a half-normal distribution tend to underestimate the origin Vertex of morning prism and overestimate the Terminal Vertex of evening prism over 50 and 30 min for Shanghai and Houston samples, respectively. The empirical results show the importance of choosing an appropriate distributional assumption for the inefficiency term in the SFM for better understanding the relation between individuals’ departure/arrival time and time-space prism vertices. The SFM based on an appropriate distributional assumption can be applied in activity-based models for big cities to better reflect tighter temporal constraints on metropolitan residents and narrower time-space prisms for outdoor activity arrangement.
