Home
University of Bergen
Martin Vatshelle's picture

Martin Vatshelle

Associate Professor
Department of Informatics
Home Page
  • E-mailMartin.Vatshelle@uib.no
  • Visitor Address
    Høyteknologisenteret i Bergen, Thormøhlensgate 55, N-5008 Bergen
    Bergen
    Room 
    3151
  • Postal Address
    Postboks 7803
    5020 Bergen
Journal articles
  • Keil, J. Mark; Mitchell, Joseph S.B.; Pradhan, Dinabandhu; Vatshelle, Martin. 2017. An algorithm for the maximum weight independent set problem on outerstring graphs. Computational geometry. 60: 19-25. doi: 10.1016/j.comgeo.2016.05.001
  • Sæther, Sigve Hortemo; Vatshelle, Martin. 2016. Hardness of computing width parameters based on branch decompositions over the vertex set. Theoretical Computer Science. 615: 120-125. doi: 10.1016/j.tcs.2015.11.039
  • Sæther, Sigve Hortemo; Telle, Jan Arne; Vatshelle, Martin. 2015. Solving #SAT and MaxSAT by dynamic programming. The journal of artificial intelligence research. 54: 59-82.
  • Sæther, Sigve Hortemo; Vatshelle, Martin. 2015. Hardness of computing width parameters based on branch decompositions over the vertex set. Electronic Notes in Discrete Mathematics. 49: 301-308. doi: 10.1016/j.endm.2015.06.041
  • Jansen, Bart Maarten Paul; Raman, Venkatesh; Vatshelle, Martin. 2014. Parameter ecology for Feedback Vertex Set. Tsinghua Science and Technology. 19: 387-409. doi: 10.1109/TST.2014.6867520
  • Oum, Sang-il; Sæther, Sigve Hortemo; Vatshelle, Martin. 2014. Faster algorithms for vertex partitioning problems parameterized by clique-width. Theoretical Computer Science. 535: 16-24. doi: 10.1016/j.tcs.2014.03.024
  • Telle, Jan Arne; Vatshelle, Martin; Sæther, Sigve Hortemo. 2014. Solving MAXSAT and #SAT on structured CNF formulas. Lecture Notes in Computer Science. 8561 LNCS: 16-31. doi: 10.1007/978-3-319-09284-3_3
  • Bui-Xuan, Binh-Minh; Telle, Jan Arne; Vatshelle, Martin. 2013. Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems. Theoretical Computer Science. 511: 66-76. doi: 10.1016/j.tcs.2013.01.009
  • Rabinovich, Yuri; Telle, Jan Arne; Vatshelle, Martin. 2013. Upper bounds on boolean-width with applications to exact algorithms. Lecture Notes in Computer Science. 8246: 308-320. doi: 10.1007/978-3-319-03898-8_26
  • Telle, Jan Arne; Suchy, Ondra; Bui-Xuan, Binh-Minh; Vatshelle, Martin. 2013. Feedback vertex set on graphs of low cliquewidth. European journal of combinatorics (Print). 34: 666-679. doi: 10.1016/j.ejc.2012.07.023
  • Vatshelle, Martin; Belmonte, Rémy. 2013. Graph classes with structured neighborhoods and algorithmic applications. Theoretical Computer Science. 511: 54-65. Published 2013-11-04. doi: 10.1016/j.tcs.2013.01.011
  • Fomin, Fedor; Gaspers, Serge; Golovach, Petr; Suchan, Karol; Szeider, Stefan; van Leeuwen, Erik Jan; Vatshelle, Martin; Villanger, Yngve. 2012. k-Gap Interval Graphs. Lecture Notes in Computer Science. 7256: 350-361.
  • Telle, Jan Arne; Vatshelle, Martin; Hvidevold, Eivind; Sharmin, Sadia. 2012. Finding good decompositions for dynamic programming on dense graphs. Lecture Notes in Computer Science. 7112: 219-231. doi: 10.1007/978-3-642-28050-4_18
  • Belmonte, Rémy; Vatshelle, Martin. 2011. Graph Classes with Structured Neighbourhoods and Algorithmic Applications. Lecture Notes in Computer Science. 6987: 47-58. doi: 10.1007/978-3-642-25870-1_6
  • Bui-Xuan, Binh-Minh; Telle, Jan Arne; Vatshelle, Martin. 2011. Boolean-width of graphs. Theoretical Computer Science. 412: 5187-5204. doi: 10.1016/j.tcs.2011.05.022
  • Adler, Isolde Marianne; Bui-Xuan, Binh-Minh; Telle, Jan Arne; Rabinovich, Yuri; Renault, Gabriel; Vatshelle, Martin. 2010. On the boolean-width of a graph: structure and applications. Lecture Notes in Computer Science. 6410: 159-170. doi: 10.1007/978-3-642-16926-7_16
  • Bodlaender, Hans L.; Van Leeuwen, Erik Jan; van Rooij, Johan M. M.; Vatshelle, Martin. 2010. Faster Algorithms on Branch and Clique Decompositions. Lecture Notes in Computer Science. 6281: 174-185. doi: 10.1007/978-3-642-15155-2_17
  • Bui-Xuan, Binh-Minh; Telle, Jan Arne; Vatshelle, Martin. 2010. H-join decomposable graphs and algorithms with runtime single exponential in rankwidth. Discrete Applied Mathematics. 158: 809-819. doi: 10.1016/j.dam.2009.09.009
  • Meister, Daniel; Telle, Jan Arne; Vatshelle, Martin. 2010. Recognizing digraphs of Kelly-width 2. Discrete Applied Mathematics. 158: 741-746. doi: 10.1016/j.dam.2009.09.018
  • Bui-Xuan, Binh-Minh; Telle, Jan Arne; Vatshelle, Martin. 2009. Boolean-width of graphs. Lecture Notes in Computer Science. 5917: 61-74. doi: 10.1007/978-3-642-11269-0_5
  • Telle, Jan Arne; Bui-Xuan, Binh-Minh; Vatshelle, Martin. 2009. Feedback Vertex Set on Graphs of low Cliquewidth. Lecture Notes in Computer Science. 5874: 113-124. doi: 10.1007/978-3-642-10217-2_14
  • Telle, Jan Arne; Meister, Daniel; Vatshelle, Martin. 2007. Characterization and recognition of graphs of bounded Kelly-width. Lecture Notes in Computer Science. 4769: 270-279.
Reports and theses
  • Vatshelle, Martin. 2012. New Width Parameters of Graphs. University of Bergen.
Book sections
  • Biedl, Therese; Vatshelle, Martin. 2012. The point-set embeddability problem for plane graphs. artikkel, pages 41-50. In:
    • Dey, Tamal; Sue, Whitesides. 2012. Proceedings of the 2012 symposuim on Computational Geometry. Association for Computing Machinery (ACM). 422 pages. ISBN: 978-1-4503-1299-8.

More information in national current research information system (CRIStin)