RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Tr. Inst. Mat.:
Year:
Volume:
Issue:
Page:
Find






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


Tr. Inst. Mat., 2011, Volume 19, Number 2, Pages 69–81 (Mi timb152)  

This article is cited in 3 scientific papers (total in 3 papers)

Algorithms for finding biclique covers of graphs with bounded pathwidth

V. V. Lepin, O. I. Duginov

Institute of Mathematics of the National Academy of Sciences of Belarus

Abstract: In this paper we present space-efficient algorithms for solving construction variants of biclique cover problems on graphs with bounded pathwidth. A biclique is a complete bipartite subgraph of a graph. Algorithms for solving the problem of finding a biclique cover with minimal degree and the problem of finding a biclique cover with minimal number of bicliques on this type of graphs in $O(n\log n)$ time with $O(\log n)$ additional memory are given.

Full text: PDF file (230 kB)
References: PDF file   HTML file
UDC: 519.1
Received: 21.09.2011

Citation: V. V. Lepin, O. I. Duginov, “Algorithms for finding biclique covers of graphs with bounded pathwidth”, Tr. Inst. Mat., 19:2 (2011), 69–81

Citation in format AMSBIB
\Bibitem{LepDug11}
\by V.~V.~Lepin, O.~I.~Duginov
\paper Algorithms for finding biclique covers of graphs with bounded pathwidth
\jour Tr. Inst. Mat.
\yr 2011
\vol 19
\issue 2
\pages 69--81
\mathnet{http://mi.mathnet.ru/timb152}


Linking options:
  • http://mi.mathnet.ru/eng/timb152
  • http://mi.mathnet.ru/eng/timb/v19/i2/p69

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. V. V. Lepin, O. I. Duginov, “O chisle biklikovogo pokrytiya dekartova proizvedeniya grafov”, Tr. In-ta matem., 21:1 (2013), 78–87  mathnet
    2. V. V. Lepin, O. I. Duginov, “Zadachi i invarianty, svyazannye s biklikami i multiklikami grafa”, Tr. In-ta matem., 21:2 (2013), 103–127  mathnet
    3. O. I. Duginov, “Slozhnost zadach pokrytiya grafa naimenshim chislom polnykh dvudolnykh grafov”, Tr. In-ta matem., 22:1 (2014), 51–69  mathnet
  • Труды Института математики
    Number of views:
    This page:319
    Full text:141
    References:29

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020