Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS


Vestnik Moskov. Univ. Ser. 1. Mat. Mekh.:
Year:
Volume:
Issue:
Page:
Find




Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register

Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika, 2021, Number 1, Pages 55–57 (Mi vmumm4379)  
Short notes

On the complexity of a linear ordering of weighted directed acyclic graphs

M. I. Shekalev, G. V. Bokov, V. B. Kudryavtsev

Lomonosov Moscow State University, Faculty of Mechanics and Mathematics
Full-text PDF (322 kB)
References:
PDF
HTML
Abstract: The paper is focused on weighted directed acyclic graphs with edges weighted with nonnegative integers. The complexity of linear ordering of vertices is considered for these graphs with respect to topological sorting. An accurate estimate of the Shannon function for the complexity of linear ordering of vertices for weighted directed acyclic graphs is obtained.
Key words: weighted directed acyclic graphs, linear ordering of vertices, topological sorting, complexity, Shannon's function.
Received: 30.10.2019
English version:
Moscow University Mathematics Bulletin, 2021, Volume 76, Issue 1, Pages 35–36
DOI: https://doi.org/10.3103/S0027132221010071
Bibliographic databases:
Document Type: Article
UDC: 510.52
Language: Russian
Citation: M. I. Shekalev, G. V. Bokov, V. B. Kudryavtsev, “On the complexity of a linear ordering of weighted directed acyclic graphs”, Vestnik Moskov. Univ. Ser. 1. Mat. Mekh., 2021, no. 1, 55–57; Moscow University Mathematics Bulletin, 76:1 (2021), 35–36
Citation in format AMSBIB
\Bibitem{SheBokKud21}
\by M.~I.~Shekalev, G.~V.~Bokov, V.~B.~Kudryavtsev
\paper On the complexity of a linear ordering of weighted directed acyclic graphs
\jour Vestnik Moskov. Univ. Ser.~1. Mat. Mekh.
\yr 2021
\issue 1
\pages 55--57
\mathnet{http://mi.mathnet.ru/vmumm4379}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=4288431}
\zmath{https://zbmath.org/?q=an:1472.05065}
\transl
\jour Moscow University Mathematics Bulletin
\yr 2021
\vol 76
\issue 1
\pages 35--36
\crossref{https://doi.org/10.3103/S0027132221010071}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000671348300006}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85109712239}
Linking options:
  • https://www.mathnet.ru/eng/vmumm4379
  • https://www.mathnet.ru/eng/vmumm/y2021/i1/p55
    • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Statistics & downloads:
    Abstract page:104
    Full-text PDF :14
    References:32
    First page:8
     
      Contact us:
    		  Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024