Search

Your search keyword '"Common neighbor"' showing total 4 results
Start Over Descriptor "Common neighbor" Publisher hal ccsd
4 results on '"Common neighbor"'

1. Finding a potential community in networks

Author

Zsolt Tuza, Cristina Bazgan, Thomas Pontoizeau, Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (LAMSADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Department of Computer Science and Systems Technology [Veszprem], and University of Panninia

Subjects
General Computer Science, Independent set, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Graph, Theoretical Computer Science, law.invention, Combinatorics, symbols.namesake, law, Line graph, 0202 electrical engineering, electronic engineering, information engineering, [INFO]Computer Science [cs], Mathematics, Complexity, Planar graph, Treewidth, Algorithm, 010201 computation theory & mathematics, Bounded function, Common neighbor, symbols, Bipartite graph, 020201 artificial intelligence & image processing, Inapproximability
Abstract

An independent 2-clique of a graph is a subset of vertices that is an independent set and such that any two vertices inside have a common neighbor outside. In this paper, we study the complexity of finding an independent 2-clique of maximum size in several graph classes and we compare it with the complexity of maximum independent set. We prove that this problem is NP-hard on apex graphs, APX-hard on line graphs, not n 1 / 2 − ϵ -approximable on bipartite graphs and not n 1 − ϵ -approximable on split graphs, while it is polynomial-time solvable on graphs of bounded degree and their complements, graphs of bounded treewidth, planar graphs, ( C 3 , C 6 ) -free graphs, threshold graphs, interval graphs and cographs.

Published
2019

2. Exact Algorithms for L(2,1)-Labeling of Graphs

Author

Martin Klazar, Mathieu Liedloff, Jan Kratochvíl, Frédéric Havet, Dieter Kratsch, Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Department of Applied Mathematics (KAM) (KAM), Univerzita Karlova v Praze, Laboratoire d'Informatique Théorique et Appliquée (LITA), Université de Lorraine (UL), Laboratoire d'Informatique Fondamentale d'Orléans (LIFO), Ecole Nationale Supérieure d'Ingénieurs de Bourges-Université d'Orléans (UO), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), and Université d'Orléans (UO)-Ecole Nationale Supérieure d'Ingénieurs de Bourges

Subjects
Vertex (graph theory), Discrete mathematics, 021103 operations research, General Computer Science, Applied Mathematics, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0211 other engineering and technologies, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Graph, Computer Science Applications, Exponential function, Running time, Combinatorics, Dynamic programming, Exact algorithm, 010201 computation theory & mathematics, Common neighbor, Theory of computation, Algorithm, Mathematics
Abstract

International audience; The notion of distance constrained graph labelings, motivated by the Frequency Assignment Problem, reads as follows: A mapping from the vertex set of a graph $G=(V,E)$ into an interval of integers $\{0, \dots ,k\}$ is an $L(2,1)$-labeling of $G$ of span $k$ if any two adjacent vertices are mapped onto integers that are at least 2 apart, and every two vertices with a common neighbor are mapped onto distinct integers. It is known that for any fixed $k\ge 4$, deciding the existence of such a labeling is an NP-complete problem. We present exact exponential time algorithms that are faster than the naive $O^*((k+1)^n)$ algorithm that would try all possible mappings. The improvement is best seen in the first NP-complete case of $k=4$, where the running time of our algorithm is $O(1.3006^n)$. Furthermore we show that dynamic programming can be used to establish an $O(3.8730^n)$ algorithm to compute an optimal $L(2,1)$-labeling.

Published
2011

3. Pressure effects on icosahedral short range order in undercooled copper

Author

Andrea Di Cicco, Federica Coppari, Massimo Celino, Italian National agency for new technologies, Energy and sustainable economic development [Frascati] (ENEA), Institut de minéralogie et de physique des milieux condensés (IMPMC), Université Pierre et Marie Curie - Paris 6 (UPMC)-Université Paris Diderot - Paris 7 (UPD7)-Institut de Physique du Globe de Paris (IPG Paris)-Centre National de la Recherche Scientifique (CNRS), CNISM, Department of Physics, University of Camerino, CNISM, Université Pierre et Marie Curie - Paris 6 (UPMC)-IPG PARIS-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), CNISM, CNR-INFMSOFT, Dipartimentodi Fisica, Universita`di Camerino, and Università degli Studi di Camerino (UNICAM)

Subjects
Icosahedral symmetry, XAS, ISRO, chemistry.chemical_element, 02 engineering and technology, Molecular dynamics, 01 natural sciences, Condensed Matter::Materials Science, 0103 physical sciences, Physics::Atomic and Molecular Clusters, General Materials Science, 010306 general physics, Supercooling, Nonlinear Sciences::Pattern Formation and Solitons, X-ray absorption spectroscopy, Chemistry, Liquid copper, General Chemistry, 021001 nanoscience & nanotechnology, Condensed Matter Physics, Copper, Chemical physics, Metals, Common neighbor, [PHYS.COND.CM-GEN]Physics [physics]/Condensed Matter [cond-mat]/Other [cond-mat.other], Short range order, [PHYS.COND.CM-MS]Physics [physics]/Condensed Matter [cond-mat]/Materials Science [cond-mat.mtrl-sci], Physical chemistry, Moleculardynamics, 0210 nano-technology
Abstract

International audience; There is not a wide consensus on the role played by the icosahedral short range order on the stability of undercooled simple metals. The scenario is even less clear for undercooled metals under external pressure. Classical molecular dynamics simulations are performed to explain experimental results recently obtained on liquid and undercooled liquid copper under pressure. The atomic configurations are characterized by a common neighbor analysis to reveal the icosahedral short range order and its relation with external pressure. External pressure increases the probability to find atomic bonds with icosahedral symmetry both in the liquid and in the undercooled copper.

Published
2010

4. Partially Square Graphs, Hamiltonicity and Circumference II

Author

Hamamache Kheddouci, Equipe, Graphe Liesp, Laboratoire d'Informatique pour l'Entreprise et les Systèmes de Production (LIESP), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), and Université de Lyon

Subjects
Discrete mathematics, Applied Mathematics, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Circumference, Distance-regular graph, Graph, Combinatorics, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Graph power, Independent set, Common neighbor, Discrete Mathematics and Combinatorics, Bound graph, ComputingMilieux_MISCELLANEOUS, Mathematics
Abstract

Given a graph G, its partially square graph G∗ is a graph obtained by adding an edge uv for each pair u, v of vertices of G at distance 2 whenever the vertices u and v have a common neighbor x satisfying the condition NG(x) ⊆ NG[u] ∪ NG[v], where NG[x]= NG(x) ∪ {x}. In case G is a claw-free graph, G∗ is equal to G2, We define σ ∗ t = min{ ∑ x∈ d ∗ G (x): S is an independent set in G ∗ and ∣S∣ = t} , where d ∗ G (x) = ∣{y ∈ V∣ xy ∈ E(G∗)}∣ . We give for hamiltonicity and circumference new sufficient conditions depending on and we improve some known results.

Published
2000

Catalog

Books, media, physical & digital resources
See catalog results