Result: Enumerating disjunctions and conjunctions of paths and cuts in reliability theory

Title:
Enumerating disjunctions and conjunctions of paths and cuts in reliability theory
Authors:
KHACHIYAN, Leonid, BOROS, Endre, ELBASSIONI, Khaled, GURVICH, Vladimir, MAKINO, Kazuhisa
Source:
29th symposium on mathematical foundations of computer science MFCS 2004Discrete applied mathematics. 155(2):137-149
Publisher Information:
Amsterdam; Lausanne; New York, NY: Elsevier, 2007.
Publication Year:
2007
Physical Description:
print, 16 ref
Original Material:
INIST-CNRS
Subject Terms:
Control theory, operational research, Automatique, recherche opérationnelle, Computer science, Informatique, Mathematics, Mathématiques, Sciences exactes et technologie, Exact sciences and technology, Sciences et techniques communes, Sciences and techniques of general use, Mathematiques, Mathematics, Combinatoire. Structures ordonnées, Combinatorics. Ordered structures, Combinatoire, Combinatorics, Théorie des graphes, Graph theory, Sciences appliquees, Applied sciences, Recherche operationnelle. Gestion, Operational research. Management science, Recherche opérationnelle et modèles formalisés de gestion, Operational research and scientific management, Théorie de la fiabilité. Renouvellement des équipements, Reliability theory. Replacement problems, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Algorithmique. Calculabilité. Arithmétique ordinateur, Algorithmics. Computability. Computer arithmetics, Combinatoire, Combinatorics, Combinatoria, Complexité, Complexity, Complejidad, Coupe graphe, Graph cut, Corte grafo, Disjonction, Disjunction, Disyunción, Graphe non orienté, Non directed graph, Grafo no orientado, Graphe orienté, Directed graph, Grafo orientado, Informatique théorique, Computer theory, Informática teórica, Problème direct, Direct problem, Problema directo, Sommet graphe, Vertex(graph), Vértice grafo, Théorie fiabilité, Reliability theory, Algorithme incrémental, Algorithme temps polynomial, Conjonction, Digraphe, Ensemble contour, Edge set, Ensemble minimal, Enumération découpe et chemin, Path and cut enumeration, Disjunction and conjunctions of paths and cuts: Reliability theory
Document Type:
Conference Conference Paper
File Description:
text
Language:
English
Author Affiliations:
Department of Computer Science, Rutgers University, 110 Frelinghuysen Road, Piscataway, NJ 08854-8004, United States
RUTCOR, Rutgers University, 640 Bartholomew Road, Piscataway, NJ 08854-8003, United States
Max-Planck-Institut für Informatik, 66123 Saarbrücken, Germany
Department of Mathematical Informatics. Graduate School of Information and Technology, University of Tokyo, Tokyo 113-8656, Japan
ISSN:
0166-218X
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=18454949
Rights:
Copyright 2007 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems

Mathematics

Operational research. Management
Accession Number:
edscal.18454949
Database:
PASCAL Archive

Further Information

Let G = (V, E) be a (directed) graph with vertex set V and edge (arc) set E. Given a set J of source-sink pairs of vertices of G, an important problem that arises in the computation of network reliability is the enumeration of minimal subsets of edges (arcs) that connect/disconnect all/at least one of the given source-sink pairs of J. For undirected graphs, we show that the enumeration problems for conjunctions of paths and disjunctions of cuts can be solved in incremental polynomial time. Furthermore, under the assumption that J consists of all pairs within a given vertex set, we also give incremental polynomial time algorithm for enumerating all minimal path disjunctions and cut conjunctions. For directed graphs, the enumeration problem for cut disjunction is known to be NP-complete. We extend this result to path conjunctions and path disjunctions, leaving open the complexity of the enumeration of cut conjunctions. Finally, we give a polynomial delay algorithm for enumerating all minimal sets of arcs connecting two given nodes s1 and s2 to, respectively, a given vertex t1, and each vertex of a given subset of vertices T2.