Search

Your search keyword '"Haddad, Mohammed"' showing total 4 results
Start Over Author "Haddad, Mohammed" Topic discrete mathematics (cs.dm)
4 results on '"Haddad, Mohammed"'

1. Hypergraphs with Polynomial Representation: Introducing $r$-splits

Author

Haddad, Mohammed, Pitois, François, Seba, Hamida, and Togni, Olivier

Subjects
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Computer Science - Discrete Mathematics
Abstract

Inspired by the split decomposition of graphs and rank-width, we introduce the notion of $r$-splits. We focus on the family of $r$-splits of a graph of order $n$, and we prove that it forms a hypergraph with several properties. We prove that such hypergraphs can be represented using only $\mathcal O(n^{r+1})$ of its hyperedges, despite its potentially exponential number of hyperedges. We also prove that there exist hypergraphs that need at least $\Omega(n^r)$ hyperedges to be represented, using a generalization of set orthogonality.

Published
2022
Full Text
View/download PDF

2. A Neighborhood-preserving Graph Summarization

Author

KIOUCHE, Abd Errahmane, Baste, Julien, Haddad, Mohammed, Seba, Hamida, Graphes, AlgOrithmes et AppLications (GOAL), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Université Lumière - Lyon 2 (UL2), Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), ANR, ANR-20-CE23-0002,COREGRAPHIE,COmpression de REseaux et de GRAPHes pour une Informatique Efficace(2020), Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), and Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)

Subjects
Social and Information Networks (cs.SI), FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Computer Science - Data Structures and Algorithms, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-OH]Computer Science [cs]/Other [cs.OH], Data Structures and Algorithms (cs.DS), Computer Science - Social and Information Networks, Computer Science - Discrete Mathematics, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract

We introduce in this paper a new summarization method for large graphs. Our summarization approach retains only a user-specified proportion of the neighbors of each node in the graph. Our main aim is to simplify large graphs so that they can be analyzed and processed effectively while preserving as many of the node neighborhood properties as possible. Since many graph algorithms are based on the neighborhood information available for each node, the idea is to produce a smaller graph which can be used to allow these algorithms to handle large graphs and run faster while providing good approximations. Moreover, our compression allows users to control the size of the compressed graph by adjusting the amount of information loss that can be tolerated. The experiments conducted on various real and synthetic graphs show that our compression reduces considerably the size of the graphs. Moreover, we conducted several experiments on the obtained summaries using various graph algorithms and applications, such as node embedding, graph classification and shortest path approximations. The obtained results show interesting trade-offs between the algorithms runtime speed-up and the precision loss., 17 pages, 10 figures

Published
2021

3. Complexity of Edge Monitoring on Some Graph Classes

Author

Bagan, Guillaume, Beggas, Fairouz, Haddad, Mohammed, Kheddouci, Hamamache, Graphes, AlgOrithmes et AppLications (GOAL), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Université Lumière - Lyon 2 (UL2), and Haddad, Mohammed

Subjects
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Applied Mathematics, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Discrete Mathematics and Combinatorics, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], Computer Science - Discrete Mathematics, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract

In this paper, we study the complexity of the edge monitoring problem. A vertex $v$ monitors an edge $e$ if both extremities together with $v$ form a triangle in the graph. Given a graph $G=(V,E)$ and a weight function on edges $c$ where $c(e)$ is the number of monitors that needs the edge $e$, the problem is to seek a minimum subset of monitors $S$ such that every edge $e$ in the graph is monitored by at least $c(e)$ vertices in $S$. In this paper, we study the edge monitoring problem on several graph classes such as complete graphs, block graphs, cographs, split graphs, interval graphs and planar graphs. We also generalize the problem by adding weights on vertices.

Published
2017
Full Text
View/download PDF

4. [1,2]-Domination in Generalized Petersen Graphs

Author

Hamamache Kheddouci, Volker Turau, Fairouz Beggas, Mohammed Haddad, Graphes, AlgOrithmes et AppLications (GOAL), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Université Lumière - Lyon 2 (UL2), and Haddad, Mohammed

Subjects
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 01 natural sciences, Combinatorics, 2]-total domination, FOS: Mathematics, 2]-domination, Computer Science::General Literature, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, Vertex domination, 0101 mathematics, ComputingMilieux_MISCELLANEOUS, Mathematics, Computer Science::Information Retrieval, 010102 general mathematics, Astrophysics::Instrumentation and Methods for Astrophysics, Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing), Generalized Petersen graph, 16. Peace & justice, Graph, Vertex (geometry), TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES, 010201 computation theory & mathematics, ComputingMethodologies_DOCUMENTANDTEXTPROCESSING, [1, Combinatorics (math.CO), Computer Science - Discrete Mathematics
Abstract

A vertex subset [Formula: see text] of a graph [Formula: see text] is a [Formula: see text]-dominating set if each vertex of [Formula: see text] is adjacent to either one or two vertices in [Formula: see text]. The minimum cardinality of a [Formula: see text]-dominating set of [Formula: see text], denoted by [Formula: see text], is called the [Formula: see text]-domination number of [Formula: see text]. In this paper, the [Formula: see text]-domination and the [Formula: see text]-total domination numbers of the generalized Petersen graphs [Formula: see text] are determined.

Published
2019
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results