본문 바로가기
KERD
논문KCI 등재

Distributive lattice polymorphisms on reflexive graphs

시거스, 마크 할버
대한수학회 (The Korean Mathematical Society)|2018.01|대한수학회보 (Bulletin of the KMS)|제55권 제1호|pp. 81-105

0

조회

0

다운로드

1

인용

0

참고문헌

키워드

recognitionCSPlattice polymorphismdistributive latticereflexive graph
주제분류수학

초록

In this paper we give two characterisations of the class of reflexive graphs admitting {\em distributive lattice polymorphisms} and use these characterisations to address the problem of recognition: we find a polynomial time algorithm to decide if a given reflexive graph $G$, in which no two vertices have the same neighbourhood, admits a distributive lattice polymorphism.

Abstract

In this paper we give two characterisations of the class of reflexive graphs admitting {\em distributive lattice polymorphisms} and use these characterisations to address the problem of recognition: we find a polynomial time algorithm to decide if a given reflexive graph $G$, in which no two vertices have the same neighbourhood, admits a distributive lattice polymorphism.

참고문헌 (18)

  1. H. Bandelt, "Graphs with edge-preserving majority functions", Discrete Math., 103(1), pp.1~5 (1992)[DOI]
  2. G. Birkhoff, "Rings of sets", Duke Math. J., 3(3), pp.443~454 (1937)[DOI]
  3. A. Bulatov, "Classifying the complexity of constraints using finite algebras", SIAM J. Comput., 34(3), pp.720~742 (2005)[DOI]
  4. C. Caravalho, "Caterpillar duality for constraint satisfaction problems", LICS '08, pp.307~316 (2008)
  5. D. Corneil, "Simple linear time recognition of unit interval graphs", Inform. Process. Lett., 55(2), pp.99~104 (1995)[DOI]
  6. R. Dilworth, "A decomposition theorem for partially ordered sets", Ann. of Math., 51, pp.161~166 (1950)[DOI]
  7. W. Dorfler, "Uber das starke Produkt von endlichen Graphen", Osterreich. Akad. Wiss. Math.-Nature Kl.S.-B. II, 178, pp.247~262 (1970)
  8. T. Feder, "Graphs admitting k-NU operations. Part 1: The Re exive Case", SIAM J. Discrete Math., 27(4), pp.1940~1963 (2013)[DOI]
  9. T. Feder, "The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory", SIAM J. Comput., 28, pp.57~104 (1998)[DOI]
  10. J. Feigenbaum, "Finding the prime factors of strong direct product graphs in polynomial time", Discrete Math., 109(1-3), pp.77~102 (1992)[DOI]
  11. F. Gardi, "A note on the Roberts characterization of proper and unit interval graphs", Discrete Math., 307, pp.2906~2908 (2007)[DOI]
  12. R. Hammack, "Handbook of product graphs, 2nd Edition" (2011), CRC Press
  13. P. Hell, "Retractions de graphes", pp.1972
  14. P. Hell, "Semilattice Polymorphisms and Chordal Graphs", European J. Combin., 36, pp.694~706 (2014)[DOI]
  15. D. Y. Hong, "A solution to the two-dimensional lattice blow-up game"
  16. E. Jawhari, "Retracts: graphs and ordered sets from the metric point of view, Combinatorics and ordered sets (Arcata, Calif., 1985)", Contemp. Math., 57, pp.175~226 (1986), Amer. Math. Soc.
  17. I. Rival, "Maximal sublattices of nite distributive lattices. II", Proc. Amer. Math. Soc., 44, pp.263~268 (1974)
  18. M. Siggers, "On the representation of finite distributive lattices", Kyungpook Math. J.

관련 논문AI추천

Towards A Dichotomy for the List Switch Homomorphism Problem for Signed Graph김효빈, 시거스, 마크 할버경북대학교 자연과학대학 수학과 · Kyungpook Mathematical Journal2023 · 제63권 제3호When the Comaximal Graph of a Lattice is ToroidalKazem Khashyarmanesh, Khadijeh Ahmad Javaheri, Mojgan Afkhami경북대학교 자연과학대학 수학과 · Kyungpook Mathematical Journal2016 · 제56권 제3호On the Toroidal Comaximal Graph of LatticesAtossa Parsapour, Khadijeh Ahmad Javaheri경북대학교 자연과학대학 수학과 · Kyungpook Mathematical Journal2018 · 제58권 제3호A Property of the Weak Subalgebra Lattice for Algebras with Some Non-EqualitiesKonrad Pioro경북대학교 자연과학대학 수학과 · Kyungpook Mathematical Journal2010 · 제50권 제2호Line semigraph of a semigraphB. Y. Bam, C. M. Deshpande, N. S. Bhave장전수학회 · Advanced Studies in Contemporary Mathematics2009 · 제18권 제2호On The Representations of Finite Distributive Lattices시거스, 마크 할버경북대학교 자연과학대학 수학과 · Kyungpook Mathematical Journal2020 · 제60권 제1호

이 간행물의 다른 논문 (21건)

A geometric inequality on a compact domain in $\mathbb R^{n}$조용승, 채영도pp. 1-8Operator fractional Brownian sheet and martingale differencesLiangwen Xia, Hongshuai Dai, Guangjun Shenpp. 9-23A structure of noncentral idempotentsZhelin Piao, 조은경, 이양, 곽태근, 서연숙pp. 25-40Multiplication operators on Bergman spaces over polydisks associated with integer matrixHansong Huang, Hui Danpp. 41-50On some special difference equations of Malmquist typeZhang Jiepp. 51-61
원문 보기