Home
University of Bergen
Pinar Heggernes's picture

Pinar Heggernes

Head of Department
Department of Informatics
Home Page
  • E-mailPinar.Heggernes@uib.no
  • Phone+47 55 58 41 75+47 924 82 316
  • Visitor Address
    HIB - Thormøhlensgt. 55
  • Postal Address
    Postboks 7803
    5020 Bergen
Books
  • Cygan, Marek; Heggernes, Pinar. 2016. Special Issue on IPEC 2014. Springer. 180 pages.
  • Heggernes, Pinar. 2016. Graph-Theoretic Concepts in Computer Science - 42nd International Workshop, WG 2016, Istanbul, Turkey, June 22-24, 2016, Revised Selected Papers. Springer. 310 pages. ISBN: 978-3-662-53535-6.
  • Heggernes, Pinar; Proskurowski, Andrzej; Thilikos, Dimitrios M. 2016. Sixth Workshop on Graph Classes, Optimization, and Width Parameters, Santorini, Greece, October 2013. Elsevier. 230 pages.
Journal articles
  • Golovach, Petr; Heggernes, Pinar; Kanté, Mamadou Moustapha; Kratsch, Dieter; Sæther, Sigve Hortemo; Villanger, Yngve. 2018. Output-Polynomial Enumeration on Graphs of Bounded (Local) Linear MIM-Width. Algorithmica. 80: 714-741.
  • Golovach, Petr; Heggernes, Pinar; Konstantinidis, Athanasios; T. Lima, Paloma; Papadopoulos, Charis. 2018. Parameterized Aspects of Strong Subgraph Closure. Leibniz International Proceedings in Informatics. 101: 23:1-23:13. doi: 10.4230/LIPIcs.SWAT.2018.23
  • Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter. 2018. Enumeration and Maximum Number of Minimal Connected Vertex Covers in Graphs. European journal of combinatorics (Print). 68: 132-147. doi: 10.1016/j.ejc.2017.07.015
  • Golovach, Petr; Heggernes, Pinar; Thomé de Lima, Paloma; Montealegre, Pedro. 2018. Finding connected secluded subgraphs. Leibniz International Proceedings in Informatics. 89: 1-13. doi: 10.4230/LIPIcs.IPEC.2017.18
  • Heggernes, Pinar; Issac, Davis; Lauri, Juho; T. Lima, Paloma; van Leeuwen, Erik Jan. 2018. Rainbow Vertex Coloring Bipartite Graphs and Chordal Graphs. Leibniz International Proceedings in Informatics. 117: 83:1-83:13. doi: 10.4230/LIPIcs.MFCS.2018.83
  • Brešar, Boštjan; Heggernes, Pinar; Kamiński, Marcin; Milanič, Martin; Paulusma, Daniël; Potočnik, Primož; Trotignon, Nicolas. 2017. Preface: Algorithmic Graph Theory on the Adriatic Coast. Discrete Applied Mathematics. 231: 1-3. doi: 10.1016/j.dam.2017.05.007
  • Dibek, Cemil; Ekim, Tınaz; Heggernes, Pinar. 2017. Maximum number of edges in claw-free graphs whose maximum degree and matching number are bounded. Discrete Mathematics. 340: 927-934. doi: 10.1016/j.disc.2017.01.010
  • Golovach, Petr; Heggernes, Pinar; Kanté, Mamadou Moustapha; Kratsch, Dieter; Sæther, Sigve Hortemo; Villanger, Yngve. 2017. Output-polynomial enumeration on graphs of bounded (local) linear MIM-width. Algorithmica. 80: 714-741. Published 2017-02-13. doi: 10.1007/s00453-017-0289-1
  • Golovach, Petr; Heggernes, Pinar; Kanté, Mamadou Moustapha; Kratsch, Dieter; Villanger, Yngve. 2017. Minimal dominating sets in interval graphs and trees. Discrete Applied Mathematics. 216: 162-170. doi: 10.1016/j.dam.2016.01.038
  • Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter; Lima, Paloma; Paulusma, Daniël. 2017. Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2. Lecture Notes in Computer Science. 10520 LNCS: 275-288. doi: 10.1007/978-3-319-68705-6_21
  • Golovach, Petr; Heggernes, Pinar; Lindzey, Nathan; McConnell, Ross M.; dos Santos, Vínicius Fernandes; Spinrad, Jeremy P.; Szwarcfiter, Jayme Luiz. 2017. On recognition of threshold tolerance graphs and their complements. Discrete Applied Mathematics. 216: 171-180. doi: 10.1016/j.dam.2015.01.034
  • Seker, Oylum; Heggernes, Pinar; Ekim, Tinaz; Taskin, Z Caner. 2017. Linear-time generation of random chordal graphs. Lecture Notes in Computer Science. 10236 LNCS: 442-453. doi: 10.1007/978-3-319-57586-5_37
  • Abu-Khzam, Faisal N.; Heggernes, Pinar. 2016. Enumerating minimal dominating sets in chordal graphs. Information Processing Letters. 116: 739-743. doi: 10.1016/j.ipl.2016.07.002
  • Basavaraju, Manu; Heggernes, Pinar; van 't Hof, Pim; Saei, Reza; Villanger, Yngve. 2016. Maximal induced matchings in triangle-free graphs. Journal of Graph Theory. 83: 231-250. doi: 10.1002/jgt.21994
  • Cygan, Marek; Heggernes, Pinar. 2016. Erratum to: Foreword: Special Issue on IPEC 2014 (Algorithmica, DOI 10.1007/s00453-016-0151-x). Algorithmica. 75: 257-257. doi: 10.1007/s00453-016-0161-8
  • Cygan, Marek; Heggernes, Pinar. 2016. Foreword: Special Issue on IPEC 2014. Algorithmica. 75: 255-256. doi: 10.1007/s00453-016-0151-x
  • Fomin, Fedor; Heggernes, Pinar; van Leeuwen, Erik Jan. 2016. The Firefighter problem on graph classes. Theoretical Computer Science. 613: 38-50. doi: 10.1016/j.tcs.2015.11.024
  • Golovach, Petr; Heggernes, Pinar; Kanté, Mamadou M.; Kratsch, Dieter; Villanger, Yngve. 2016. Enumerating minimal dominating sets in chordal bipartite graphs. Discrete Applied Mathematics. 199: 30-36. doi: 10.1016/j.dam.2014.12.010
  • Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter. 2016. Enumerating minimal connected dominating sets in graphs of bounded chordality. Theoretical Computer Science. 630: 63-75. doi: 10.1016/j.tcs.2016.03.026
  • Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter. 2016. Enumeration and maximum number of minimal connected vertex covers in graphs. Lecture Notes in Computer Science. 9538: 235-247. doi: 10.1007/978-3-319-29516-9_20
  • Heggernes, Pinar. 2016. Preface. Lecture Notes in Computer Science. 9941 LNCS: V-V.
  • Heggernes, Pinar; Meister, Daniel; Papadopoulos, Charis; Rotics, Udi. 2016. Clique-width of path powers. Discrete Applied Mathematics. 205: 62-72. doi: 10.1016/j.dam.2015.11.009
  • Heggernes, Pinar; Proskurowski, Andrzej; Thilikos, Dimitrios M. 2016. Foreword: Sixth Workshop on Graph Classes, Optimization, and Width Parameters, Santorini, Greece, October 2013. Discrete Applied Mathematics. 199: 1-2. doi: 10.1016/j.dam.2015.10.004
  • Bodlaender, Hans; Heggernes, Pinar; Telle, Jan Arne. 2015. Recognizability Equals Definability for Graphs of Bounded Treewidth and Bounded Chordality. Electronic Notes in Discrete Mathematics.
  • Courcelle, Bruno; Heggernes, Pinar; Meister, Daniel; Papadopoulos, Charis; Rotics, Udi. 2015. A characterisation of clique-width through nested partitions. Discrete Applied Mathematics. 187: 70-81. doi: 10.1016/j.dam.2015.02.016
  • Fernau, Henning; Heggernes, Pinar; Villanger, Yngve. 2015. A Multi-Parameter Analysis of Hard Problems on Deterministic Finite Automata. Journal of computer and system sciences (Print). 81: 747-765.
  • Fernau, Henning; Heggernes, Pinar; van 't Hof, Pim; Meister, Daniel; Saei, Reza. 2015. Computing the metric dimension for chain graphs. Information Processing Letters. 115: 671-676. doi: 10.1016/j.ipl.2015.04.006
  • Golovach, Petr; Heggernes, Pinar; Kante, Mamadou; Kratsch, Dieter; Sæther, Sigve Hortemo; Villanger, Yngve. 2015. Output-polynomial enumeration on graphs of bounded (local) linear mim-width. Lecture Notes in Computer Science. 9472: 248-258.
  • Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter. 2015. Enumerating minimal connected dominating sets in graphs of bounded chordality. Leibniz International Proceedings in Informatics. 43: 307-318. doi: 10.4230/LIPIcs.IPEC.2015.307
  • Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter; Villanger, Yngve. 2015. An incremental polynomial time algorithm to enumerate all minimal edge dominating sets. Algorithmica. 72: 836-859.
  • Golovach, Petr; Heggernes, Pinar; van 't Hof, Pim; Manne, Fredrik; Paulusma, Daniël; Pilipczuk, Michal Pawel. 2015. Modifying a graph using vertex elimination. Algorithmica. 72: 99-125.
  • Golovach, Petr; Heggernes, Pinar; van 't Hof, Pim; Paul, Christophe. 2015. Hadwiger number of graphs with small chordality. SIAM Journal on Discrete Mathematics. 29: 1427-1451. doi: 10.1137/140975279
  • Golovach, Petr; Heggernes, Pinar; van' t Hof, Pim; Paul, Christophe. 2015. Hadwiger number of graphs with small chordality. Lecture Notes in Computer Science. 8747: 201-213.
  • Heggernes, Pinar; van 't Hof, Pim; Marx, Dániel; Misra, Neeldhara; Villanger, Yngve. 2015. On the Parameterized Complexity of Finding Separators with Non-Hereditary Properties. Algorithmica. 72: 687-713. doi: 10.1007/s00453-014-9868-6
  • Heggernes, Pinar; van 't Hof, Pim; Meister, Daniel; Villanger, Yngve. 2015. Induced Subgraph Isomorphism on proper interval and bipartite permutation graphs. Theoretical Computer Science. 562: 252-269. doi: 10.1016/j.tcs.2014.10.002
  • Heggernes, Pinar; van 't Hof, Pim; van Leeuwen, Erik Jan; Saei, Reza. 2015. Finding Disjoint Paths in Split Graphs. Theory of Computing Systems. 57: 140-159. doi: 10.1007/s00224-014-9580-6
  • Basavaraju, Manu; Heggernes, Pinar; van 't Hof, Pim; Saei, Reza; Villanger, Yngve. 2014. Maximal induced matchings in triangle-free graphs. Lecture Notes in Computer Science. 8747: 93-104.
  • Belmonte, Rémy; Golovach, Petr; Heggernes, Pinar; van 't Hof, Pim; Kaminski, Marcin; Paulusma, Daniël. 2014. Detecting fixed patterns in chordal graphs in polynomial time. Algorithmica. 69: 501-521. doi: 10.1007/s00453-013-9748-5
  • Belmonte, Rémy; Heggernes, Pinar; van 't Hof, Pim; Rafiey, Arash; SaeiDinvar, Reza. 2014. Graph classes and Ramsey numbers. Discrete Applied Mathematics. 173: 16-27. doi: 10.1016/j.dam.2014.03.016
  • Berger, André; Grigoriev, Alexander; Heggernes, Pinar; Van Der Zwaan, Ruben. 2014. Scheduling unit-length jobs with precedence constraints of small height. Operations Research Letters. 42: 166-172. doi: 10.1016/j.orl.2014.01.008
  • Boros, Endre; Heggernes, Pinar; van 't Hof, Pim; Milanic, Martin. 2014. Vector connectivity in graphs. Networks. 63: 277-285. doi: 10.1002/net.21545
  • Fomin, Fedor; Heggernes, Pinar; Kratsch, Dieter; Papadopoulos, Charis; Villanger, Yngve. 2014. Enumerating minimal subset feedback vertex sets. Algorithmica. 69: 216-231. doi: 10.1007/s00453-012-9731-6
  • Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter; Rafiey, Arash. 2014. Finding clubs in graph classes. Discrete Applied Mathematics. 174: 57-65. doi: 10.1016/j.dam.2014.04.016
  • Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter; Saei, Reza. 2014. An exact algorithm for Subset Feedback Vertex Set on chordal graphs. Journal of Discrete Algorithms. 26: 7-15.
  • Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter; SaeiDinvar, Reza. 2014. Subset feedback vertex sets in chordal graphs. Journal of Discrete Algorithms. 26: 7-15. doi: 10.1016/j.jda.2013.09.005
  • Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter; Villanger, Yngve. 2014. An incremental polynomial time Algorithm to enumerate all minimal edge dominating sets. Algorithmica. 72: 836-859. Published 2014-04-08. doi: 10.1007/s00453-014-9875-7
  • Golovach, Petr; Heggernes, Pinar; Lindzey, Nathan; McConnell, Ross; Fernandes dos Santos, Vinicius; Spinrad, Jeremy. 2014. Recognizing Threshold Tolerance Graphs in O(n^2) Time. Lecture Notes in Computer Science. 8747: 214-224. doi: 10.1007/978-3-319-12340-0_18
  • Heggernes, Pinar; Kratochvil, J; Oum, SI. 2014. Guest editors' foreword. Discrete Applied Mathematics. 168: 1-2. doi: 10.1016/j.dam.2013.12.012
  • Heggernes, Pinar; van 't Hof, Pim; Lévêque, Benjamin; Lokshtanov, Daniel; Paul, Christophe. 2014. Contracting graphs to paths and trees. Algorithmica. 68: 109-132. doi: 10.1007/s00453-012-9670-2
  • Heggernes, Pinar; van 't Hof, Pim; van Leeuwen, Erik Jan; Saei, Reza. 2014. Finding disjoint paths in split graphs. Lecture Notes in Computer Science. 8327 LNCS: 315-326. doi: 10.1007/978-3-319-04298-5_28
  • Heggernes, Pinar; van 't Hof, Pim; van Leeuwen, Erik Jan; SaeiDinvar, Reza. 2014. Finding disjoint paths in split graphs. Theory of Computing Systems. 20 pages. Published 2014-09-28. doi: 10.1007/s00224-014-9580-6
  • dos Santos, Vinicius; Golovach, Petr; Heggernes, Pinar; Nathan, Lindzey; McConnell, Ross; Spinrad, Jeremy. 2014. On Recognition of Threshold Tolerance Graphs and their Complements. Lecture Notes in Computer Science. 8747: 214-224.
  • Boros, Endre; Heggernes, Pinar; van 't Hof, Pim; Milanic, Martin. 2013. Vector connectivity in graphs. Lecture Notes in Computer Science. 7876: 331-342. doi: 10.1007/978-3-642-38236-9_30
  • Couturier, Jean-François; Heggernes, Pinar; van 't Hof, Pim; Kratsch, Dieter. 2013. Minimal dominating sets in graph classes: Combinatorial bounds and enumeration. Theoretical Computer Science. 487: 82-94. doi: 10.1016/j.tcs.2013.03.026
  • Ekim, Tinaz; Heggernes, Pinar; Meister, Daniel. 2013. Polar permutation graphs are polynomial-time recognisable. European journal of combinatorics (Print). 34: 576-592. doi: 10.1016/j.ejc.2011.12.007
  • Fernau, Henning; Heggernes, Pinar; Villanger, Yngve. 2013. A Multivariate Analysis of Some DFA Problems. Lecture Notes in Computer Science. 7810: 275-286. doi: 10.1007/978-3-642-37064-9_25
  • Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter; Rafiey, Arash. 2013. Cliques and Clubs. Lecture Notes in Computer Science. 7878: 276-287.
  • Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter; Villanger, Yngve. 2013. An Incremental Polynomial Time Algorithm to Enumerate All Minimal Edge Dominating Sets. Lecture Notes in Computer Science. 7965: 285-296.
  • Golovach, Petr; Heggernes, Pinar; van 't Hof, Pim; Manne, Fredrik; Paulusma, Daniël; Pilipczuk, Michal Pawel. 2013. Modifying a Graph Using Vertex Elimination. Algorithmica. doi: 10.1007/s00453-013-9848-2
  • Golovach, Petr; Heggernes, Pinar; van 't Hof, Pim; Paulusma, Daniel. 2013. Choosability on H-free graphs. Information Processing Letters. 113: 107-110. doi: 10.1016/j.ipl.2012.12.003
  • Heggernes, Pinar; Kratsch, Dieter; Lokshtanov, Daniel; Raman, Venkatesh; Saurabh, Saket. 2013. Fixed-parameter algorithms for Cochromatic Number and Disjoint Rectangle Stabbing via iterative localization. Information and Computation. 231: 109-116. doi: 10.1016/j.ic.2013.08.007
  • Heggernes, Pinar; van 't Hof, Pim; Jansen, Bart Maarten Paul; Kratsch, Stefan; Villanger, Yngve. 2013. Parameterized complexity of vertex deletion into perfect graph classes. Theoretical Computer Science. 511: 172-180. doi: 10.1016/j.tcs.2012.03.013
  • Heggernes, Pinar; van 't Hof, Pim; Lokshtanov, Daniel; Paul, Christophe. 2013. Obtaining a bipartite graph by contracting few edges. SIAM Journal on Discrete Mathematics. 27: 2143-2156. doi: 10.1137/130907392
  • Heggernes, Pinar; van 't Hof, Pim; Milanic, Martin. 2013. Induced subtrees in interval graphs. Lecture Notes in Computer Science. 8288: 230-243.
  • Belmonte, Rémy; Heggernes, Pinar; van 't Hof, Pim. 2012. Edge contractions in subclasses of chordal graphs. Discrete Applied Mathematics. 160: 999-1010. doi: 10.1016/j.dam.2011.12.012
  • Belmonte, Rémy; Heggernes, Pinar; van 't Hof, Pim; SaeiDinvar, Reza. 2012. Ramsey Numbers for Line Graphs and Perfect Graphs. Lecture Notes in Computer Science. 7434: 204-215. doi: 10.1007/978-3-642-32241-9_18
  • Couturier, Jean-francois; Heggernes, Pinar; van 't Hof, Pim; Kratsch, Dieter. 2012. Minimal Dominating Sets in Graph Classes: Combinatorial Bounds and Enumeration. Lecture Notes in Computer Science. 7147: 202-213. doi: 10.1007/978-3-642-27660-6_17
  • Couturier, Jean-francois; Heggernes, Pinar; van 't Hof, Pim; Villanger, Yngve. 2012. Maximum Number of Minimal Feedback Vertex Sets in Chordal Graphs and Cographs. Lecture Notes in Computer Science. 7434: 133-144. doi: 10.1007/978-3-642-32241-9_12
  • Ekim, Tinaz; Erey, Aysel; Heggernes, Pinar; van 't Hof, Pim; Meister, Daniel. 2012. Computing Minimum Geodetic Sets of Proper Interval Graphs. Lecture Notes in Computer Science. 7256: 279-290. doi: 10.1007/978-3-642-29344-3_24
  • Fomin, Fedor; Heggernes, Pinar; van Leeuwen, Erik Jan. 2012. Making Life Easier for Firefighters. Lecture Notes in Computer Science. 7288: 177-188. doi: 10.1007/978-3-642-30347-0_19
  • Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter; SaeiDinvar, Reza. 2012. An Exact Algorithm for Subset Feedback Vertex Set on Chordal Graphs. Lecture Notes in Computer Science. 7535: 85-96. doi: 10.1007/978-3-642-33293-7_10
  • Golovach, Petr; Heggernes, Pinar; Mihai, Rodica. 2012. Edge search number of cographs. Discrete Applied Mathematics. 160: 734-743. doi: 10.1016/j.dam.2011.04.020
  • Golovach, Petr; Heggernes, Pinar; van 't Hof, Pim; Manne, Fredrik; Paulusma, Daniel; Pilipczuk, Michal Pawel. 2012. How to Eliminate a Graph. Lecture Notes in Computer Science. 7551: 320-331. doi: 10.1007/978-3-642-34611-8_32
  • Heggernes, Pinar; Kratochvil, Jan; Proskurowski, Andrzej. 2012. Guest editors' foreword. Discrete Applied Mathematics. 160: 683-684. doi: dx.doi.org/10.1016/j.dam.2012.01.001
  • Heggernes, Pinar; Meister, Daniel; Papadopoulos, Charis. 2012. Characterising the linear clique-width of a class of graphs by forbidden induced subgraphs. Discrete Applied Mathematics. 160: 888-901. doi: 10.1016/j.dam.2011.03.018
  • Heggernes, Pinar; Sæther, Sigve Hortemo. 2012. Broadcast Domination on Block Graphs in Linear Time. Lecture Notes in Computer Science. 7353: 172-183. doi: 10.1007/978-3-642-30642-6_17
  • Heggernes, Pinar; van 't Hof, Pim; Lokshtanov, Daniel; Nederlof, Jesper. 2012. Computing the cutwidth of bipartite permutation graphs in linear time. SIAM Journal on Discrete Mathematics. 26: 1008-1021. doi: 10.1137/110830514
  • Heggernes, Pinar; van 't Hof, Pim; Lévêque, Benjamin; Lokshtanov, Daniel; Paul, Christophe. 2012. Contracting graphs to paths and trees. Lecture Notes in Computer Science. 7112: 55-66. doi: 10.1007/978-3-642-28050-4_5
  • Heggernes, Pinar; van 't Hof, Pim; Marx, Daniel; Misra, Neeldhara; Villanger, Yngve. 2012. On the Parameterized Complexity of Finding Separators with Non-Hereditary Properties. Lecture Notes in Computer Science. 7551: 332-343. doi: 10.1007/978-3-642-34611-8_33
  • Heggernes, Pinar; van 't Hof, Pim; Paulusma, Daniel. 2012. Computing role assignments of proper interval graphs in polynomial time. Journal of Discrete Algorithms. 14: 173-188. doi: dx.doi.org/10.1016/j.jda.2011.12.004
  • Belmonte, Rémy; Golovach, Petr A.; Heggernes, Pinar; van 't Hof, Pim; Kaminski, Marcin; Paulusma, Daniel. 2011. Finding contractions and induced minors in chordal graphs via disjoint paths. Lecture Notes in Computer Science. 7074: 110-119.
  • Belmonte, Rémy; Heggernes, Pinar; van 't Hof, Pim. 2011. Edge contractions in subclasses of chordal graphs. Lecture Notes in Computer Science. 6648: 528-539.
  • Bodlaender, Hans L.; Heggernes, Pinar; Villanger, Yngve. 2011. Faster Parameterized Algorithms for Minimum Fill-in. Algorithmica. 61: 817-838. doi: 10.1007/s00453-010-9421-1
  • Bui-Xuan, Binh-Minh; Heggernes, Pinar; Meister, Daniel; Proskurowski, Andrzej. 2011. A generic approach to decomposition algorithms, with an application to digraph decomposition. Lecture Notes in Computer Science. 6842: 331-342. doi: 10.1007/978-3-642-22685-4_30
  • Fomin, Fedor; Heggernes, Pinar; Kratsch, Dieter; Papadopoulos, Charis; Villanger, Yngve. 2011. Enumerating minimal subset feedback vertex sets. Lecture Notes in Computer Science. 6844: 399-410. doi: 10.1007/978-3-642-22300-6_34
  • Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter; Lokshtanov, Daniel; Meister, Daniel; Saurabh, Saket. 2011. Bandwidth on AT-free graphs. Theoretical Computer Science. 412: 7001-7008. doi: 10.1016/j.tcs.2011.09.011
  • Heggernes, Pinar; Lokshtanov, Daniel; Mihai, Rodica; Papadopoulos, Charis. 2011. Cutwidth of Split Graphs and Threshold Graphs. SIAM Journal on Discrete Mathematics. 25: 1418-1437. doi: 10.1137/080741197
  • Heggernes, Pinar; Mancini, Federico; Papadopoulos, Charis; Sritharan, R. 2011. Strongly chordal and chordal bipartite graphs are sandwich monotone. Journal of combinatorial optimization. 22: 438-456. doi: 10.1007/s10878-010-9322-x
  • Heggernes, Pinar; Meister, Daniel; Papadopoulos, Charis. 2011. Graphs of linear clique-width at most 3. Theoretical Computer Science. 412: 5466-5486. doi: 10.1016/j.tcs.2011.06.016
  • Heggernes, Pinar; Meister, Daniel; Proskurowski, Andrzej. 2011. Computing minimum distortion embeddings into a path for bipartite permutation graphs and threshold graphs. Theoretical Computer Science. 412: 1275-1297. doi: 10.1016/j.tcs.2011.01.005
  • Heggernes, Pinar; Meister, Daniel; Rotics, Udi. 2011. Computing the clique-width of large path powers in linear time via a new characterisation of clique-width. Lecture Notes in Computer Science. 6651: 233-246. doi: 10.1007/978-3-642-20712-9_18
  • Heggernes, Pinar; van 't Hof, Pim; Jansen, Bart M. P.; Kratsch, Stefan; Villanger, Yngve. 2011. Parameterized complexity of vertex deletion into perfect graphs classes. Lecture Notes in Computer Science. 6914: 240-251.
  • Heggernes, Pinar; van 't Hof, Pim; Lévêque, Benjamin; Paul, Christophe. 2011. Contracting chordal graphs and bipartite graphs to paths and trees. Electronic Notes in Discrete Mathematics. 37: 87-92.
  • Heggernes, Pinar; van 't Hof, Pim; Paulusma, Daniel. 2011. Computing role assignments of proper interval graphs in polynomial time. Lecture Notes in Computer Science. 6460: 167-180.
  • Bodlaender, Hans L.; Fellows, Michael R.; Heggernes, Pinar; Mancini, Federico; Papadopoulos, Charis; Rosamond, Frances. 2010. Clustering with partial information. Theoretical Computer Science. 411: 1202-1211. doi: 10.1016/j.tcs.2009.12.016
  • Fomin, Fedor; Heggernes, Pinar; Mihai, Rodica. 2010. Mixed Search Number and Linear-Width of Interval and Split Graphs. Networks. 56: 207-214. doi: 10.1002/net.20373
  • Heggernes, Pinar; Kratochvil, Jan; Proskurowski, Andrzej. 2010. Guest editors' foreword. Discrete Applied Mathematics. 158: 729-730. doi: 10.1016/j.dam.2010.01.003
  • Heggernes, Pinar; Kratsch, Dieter; Lokshtanov, Daniel; Raman, Venkatesh; Saurabh, Saket. 2010. Fixed-parameter algorithms for Cochromatic Number and Disjoint Rectangle Stabbing. Lecture Notes in Computer Science. 6139: 334-345.
  • Heggernes, Pinar; Lokshtanov, Daniel; Nederlof, Jesper; Paul, Christophe; Telle, Jan Arne. 2010. Generalized graph clustering: recognizing (p,q)-cluster graphs. Lecture Notes in Computer Science. 6410: 171-183.
  • Heggernes, Pinar; Mancini, Federico; Nederlof, Jesper; Villanger, Yngve. 2010. A Parameterized Algorithm for Chordal Sandwich. Lecture Notes in Computer Science. 6078: 120-130.
  • Heggernes, Pinar; Meister, Daniel. 2010. Hardness and approximation of minimum distortion embeddings. Information Processing Letters. 110: 312-316. doi: 10.1016/j.ipl.2010.02.009
  • Heggernes, Pinar; Meister, Daniel; Rotics, Udi. 2010. Exploiting restricted linear structure to cope with the hardness of clique-width. Lecture Notes in Computer Science. 6108: 284-295.
  • Heggernes, Pinar; Meister, Daniel; Villanger, Yngve. 2010. Induced Subgraph Isomorphism on Interval and Proper Interval Graphs. Lecture Notes in Computer Science. 6507: 399-409.
  • Heggernes, Pinar; van 't Hof, Pim; Lokshtanov, Daniel; Nederlof, Jesper. 2010. Computing the cutwidth of bipartite permutation graphs in linear time. Lecture Notes in Computer Science. 6410: 75-87.
  • Ekim, Tinaz; Heggernes, Pinar; Meister, Daniel. 2009. Polar permutation graphs. Lecture Notes in Computer Science. 5874: 218-229. doi: 10.1007/978-3-642-10217-2_23
  • Fomin, Fedor; Heggernes, Pinar; Mihai, Rodica. 2009. Mixed search number and linear-width of interval and split graphs. Networks. doi: 10.1002/net.20373
  • Golovach, Petr; Heggernes, Pinar. 2009. Choosability of P5-free graphs. Lecture Notes in Computer Science. 5734: 382-391. doi: 10.1007/978-3-642-03816-7_33
  • Golovach, Petr; Heggernes, Pinar; Kratsch, Dieter; Lokshtanov, Daniel; Meister, Daniel; Saurabh, Saket. 2009. Bandwidth on AT-Free Graphs. Lecture Notes in Computer Science. 5878: 573-582. doi: 10.1007/978-3-642-10631-6_59
  • Heggernes, Pinar; Kratsch, Dieter; Meister, Daniel. 2009. Bandwidth of bipartite permutation graphs in polynomial time. Journal of Discrete Algorithms. 7: 533-544. doi: 10.1016/j.jda.2008.11.001
  • Heggernes, Pinar; Mancini, Federico. 2009. Dynamically maintaining split graphs. Discrete Applied Mathematics. 157: 2057-2069. doi: 10.1016/j.dam.2008.06.028
  • Heggernes, Pinar; Mancini, Federico. 2009. Minimal split completions. Discrete Applied Mathematics. 157: 2659-2669. doi: 10.1016/j.dam.2008.08.010
  • Heggernes, Pinar; Mancini, Federico; Papadopoulos, Charis; R., Sritharan. 2009. Strongly Chordal and Chordal Bipartite Graphs Are Sandwich Monotone. Lecture Notes in Computer Science. 5609: 398-407. doi: 10.1007/978-3-642-02882-3_40
  • Heggernes, Pinar; Meister, Daniel; Papadopoulos, Charis. 2009. A new representation of proper interval graphs with an application to clique-width. Electronic Notes in Discrete Mathematics. 32: 27-34. doi: 10.1016/j.endm.2009.02.005
  • Heggernes, Pinar; Meister, Daniel; Papadopoulos, Charis. 2009. A Complete Characterisation of the Linear Clique-Width of Path Powers. Lecture Notes in Computer Science. 5532: 241-250. doi: 10.1007/978-3-642-02017-9_27
  • Heggernes, Pinar; Mihai, Rodica. 2009. Edge search number of cographs in linear time. Lecture Notes in Computer Science. 5598: 16-26. doi: 10.1007/978-3-642-02270-8_5
  • Heggernes, Pinar; Papadopoulos, Charis. 2009. Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions. Theoretical Computer Science. 410: 1-15. doi: 10.1016/j.tcs.2008.07.020
  • Villanger, Yngve; Heggernes, Pinar; Paul, Christophe; Telle, Jan Arne. 2009. Interval completion is fixed parameter tractable. SIAM journal on computing (Print). 38: 2007-2020. doi: 10.1137/070710913
  • Berry, Anne; Dahlhaus, Elias; Heggernes, Pinar; Simonet, Genevieve. 2008. Sequential and parallel triangulating algorithms for Elimination Game and new insights on Minimum Degree. Theoretical Computer Science. 409: 601-616. doi: 10.1016/j.tcs.2008.09.059
  • Bodlaender, Hans L.; Fellows, Michael; Heggernes, Pinar; Mancini, Federico; Papadopoulos, Charis; Rosamond, Frances. 2008. Clustering with partial information. Lecture Notes in Computer Science. 5162: 144-155.
  • Bodlaender, Hans L.; Heggernes, Pinar; Villanger, Yngve. 2008. Faster Parameterized Algorithms for Minimum Fill-In. Lecture Notes in Computer Science. 5369: 282-293.
  • Heggernes, Pinar; Kratsch, Dieter. 2008. Linear-time certifying recognition algorithms and forbidden induced subgraphs. Nordic Journal of Computing. 14: 87-108.
  • Heggernes, Pinar; Kratsch, Dieter; Meister, Daniel. 2008. Bandwidth of Bipartite Permutation Graphs in Polynomial Time. Lecture Notes in Computer Science. 4957: 216-227.
  • Heggernes, Pinar; Lokshtanov, Daniel; Mihai, Rodica Georgeta; Papadopoulos, Charis. 2008. Cutwidth of split graphs, threshold graphs, and proper interval graphs. Lecture Notes in Computer Science. 5344: 218-229.
  • Heggernes, Pinar; Mancini, Federico; Papadopoulos, Charis. 2008. Minimal comparability completions of arbitrary graphs. Discrete Applied Mathematics. 156: 705-718. doi: 10.1016/j.dam.2007.08.039
  • Heggernes, Pinar; Meister, Daniel; Papadopoulos, Charis. 2008. Graphs of Linear Clique-Width at Most 3. Lecture Notes in Computer Science. 4978: 330-341.
  • Heggernes, Pinar; Meister, Daniel; Proskurowski, Andrzej. 2008. Minimum Distortion Embeddings into a Path of Bipartite Permutation and Threshold Graphs. Lecture Notes in Computer Science. 5124: 331-342.
  • Heggernes, Pinar; Mihai, Rodica Georgeta. 2008. Mixed search number of permutation graphs. Lecture Notes in Computer Science. 5059: 196-207.
  • Heggernes, Pinar; Peyton, Barry W. 2008. Fast computation of minimal fill inside a given elimination ordering. SIAM Journal on Matrix Analysis and Applications. 30: 1424-1444. doi: 10.1137/070680680
  • Fomin, Fedor; Heggernes, Pinar; Kratschz, Dieter. 2007. Exact algorithms for graph homomorphisms. Theory of Computing Systems. 41: 381-393. doi: 10.1007/s00224-007-2007-x
  • Fomin, Fedor; Heggernes, Pinar; Mihai, Rodica Georgeta. 2007. Mixed search number and linear-width of interval and split graphs. Lecture Notes in Computer Science. 4769: 304-315.
  • Heggernes, Pinar; Papadopoulos, Charis. 2007. Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions. Lecture Notes in Computer Science. 4598: 406-416.
  • Heggernes, Pinar; Suchan, Karol; Todinca, Ioan; Villanger, Yngve. 2007. Characterizing minimal interval completions: Towards better understanding of profile and pathwidth. Lecture Notes in Computer Science. 4393: 236-247.
  • Berry, Anne; Bordat, Jean-paul; Heggernes, Pinar; Simonet, Genevieve; Villanger, Yngve. 2006. A wide-range algorithm for minimal triangulation from an arbitrary ordering. Journal of Algorithms. 58: 33-66. doi: doi:10.1016/j.jalgor.2004.07.0
  • Berry, Anne; Heggernes, Pinar; Villanger, Yngve. 2006. A vertex incremental approach for maintaining chordality. Discrete Mathematics. 306: 318-336. doi: 10.1016/j.disc.2005.12.002
  • Cohen, Johanne; Fomin, Fedor; Heggernes, Pinar; Kratsch, Dieter; Kucherov, Gregory. 2006. Optimal linear arrangement of interval graphs. Lecture Notes in Computer Science. 4162,: 267-279. doi: 10.1007/11821069_24
  • Heggernes, Pinar. 2006. Minimal triangulations of graphs: A survey. Discrete Mathematics. 306: 297-317. doi: 10.1016/j.disc.2005.12.003
  • Heggernes, Pinar; Lokshtanov, Daniel. 2006. Optimal broadcast domination in polynomial time. Discrete Mathematics. 306: 3267-3280. doi: 10.1016/j.disc.2006.06.013
  • Heggernes, Pinar; Mancini, Federico. 2006. Minimal Split Completions of Graphs. Lecture Notes in Computer Science. 3887: 592-604. doi: 10.1007/11682462_55
  • Heggernes, Pinar; Mancini, Federico; Papadopoulos, Charis. 2006. Making Arbitrary Graphs Transitively Orientable: Minimal Comparability Completions. Lecture Notes in Computer Science. 4288: 419-428. doi: 10.1007/11940128_43
  • Heggernes, Pinar; Telle, Jan Arne; Villanger, Yngve. 2006. Computing Minimal Triangulations in Time O(nα log n) = o(n2.376). SIAM Journal on Discrete Mathematics. 19: 900-913.
  • Heggernes, Pinar; Villanger, Yngve. 2006. Simple and efficient modifications of elimination orderings. Lecture Notes in Computer Science. 3732: 788-797. doi: 10.1007/11558958_95
  • Mancini, Federico; Heggernes, Pinar. 2006. A completely dynamic algorithm for split graphs. Electronic Notes in Discrete Mathematics. 27: 69-70.
  • Fomin, Fedor; Heggernes, Pinar; Kratsch, Dieter. 2005. Exact algorithms for graph homomorphisms. Lecture Notes in Computer Science. 3623: 161-171.
  • Heggernes, Pinar; Lokshtanov, Daniel. 2005. Optimal broadcast domination of arbitrary graphs in polynomial time. Lecture Notes in Computer Science. 3787: 187-198. doi: 10.1007/11604686_17
  • Heggernes, Pinar; Suchan, Karol; Todinca, Ioan; Villanger, Yngve. 2005. Minimal interval completions. Lecture Notes in Computer Science. 3669: 403-414. doi: 10.1007/11561071_37
  • Berry, A; Heggernes, Pinar; Simonet, G. 2004. The minimum degree heuristic and the minimal triangulation process. Lecture Notes in Computer Science. 2880: 58-70.
  • Berry, A; Heggernes, Pinar; Villanger, Yngve. 2004. A vertex incremental approach for dynamically maintaining chordal graphs. Lecture Notes in Computer Science. 2906: 47-57.
  • Berry, Anne; Blair, Jean R S; Heggernes, Pinar; Peyton, Barry W. 2004. Maximum Cardinality Search for Computing Minimal Triangulations of Graphs. Algorithmica. 39: 287-298. doi: 10.1007/s00453-004-1084-3
  • Blair, Jean R S; Heggernes, Pinar; Horton, Steve; Manne, Fredrik. 2004. Broadcast Domination Algorithms for Interval Graphs, Series-Parallel Graphs, and Trees. Congressus Numerantium. 169: 55-77.
  • Fellows, Michael; Heggernes, Pinar; Rosamond, Frances; Sloper, Christian; Telle, Jan Arne. 2004. Finding k disjoint triangles in an arbitrary graph. Lecture Notes in Computer Science. 3353: 235-244.
  • Fomin, Fedor; Heggernes, Pinar; Telle, Jan Arne. 2004. Graph searching, elimination trees, and a generalization of bandwidth. Algorithmica. 41: 73-87. doi: 10.1007/s00453-004-1117-y
  • Fiala, Jiri; Heggernes, Pinar; Kristiansen, Petter; Telle, Jan Arne. 2003. Generalized H-coloring and H-covering of Trees. Nordic Journal of Computing. 10: 206-224.
  • Blair, Jean; Heggernes, Pinar; Telle, Jan Arne. 2001. A Practical Algorithm for Making Filled Graphs Minimal. Theoretical Computer Science. 250: 125-141.
  • Berry, Anne; Bordat, Jean-Paul; Heggernes, Pinar. 2000. Recognizing Weakly Triangulated Graphs by Edge Separability. Nordic Journal of Computing. 7: 164-177.
  • Björck, Åke; Heggernes, Pinar; Matstoms, Pontus. 2000. Methods for large scale total least squares problems. SIAM Journal on Matrix Analysis and Applications. 22: 413-429.
  • Heggernes, Pinar; Telle, Jan Arne. 1998. Partitioning graphs into generalized dominating sets. Nordic Journal of Computing. 5: 128-142.
  • Aspvall, B.; Heggernes, Pinar. 1994. Finding Minimum Height Elimination Trees for Interval Graphs in Polynomial Time. BIT Numerical Mathematics. 34: 484-509.
Reports and theses
  • Tveito, Aslak; Almås, Aslaug Grov; Goebel, Vera; Heggernes, Pinar; Ingebrigtsen, Kjell Arne; Johansen, Dag; Kløve, Torleiv; Opdahl, Andreas; Pettersen, Kristin Ytterstad; Aagesen, Finn Arve. 2004. Nyttig nysgjerrighet : Fagplan for informasjons- og kommunikasjonsteknologi (IKT). Norges Forskningsråd, Oslo. 31 pages.
  • Blair, Jean; Heggernes, Pinar; Horton, Steve; Manne, Fredrik. 2003. Broadcast domination algorithms for interval graphs, series-parallel graphs and trees. Reports in Informatics. 249. Department of Informatics, University of Bergen, Bergen, Norway.
  • Oksa, Gabriel; Becka, Martin; Vajtersic, Marian; Moe, Randi; Manne, Fredrik; Heggernes, Pinar. 2002. SCALABLE PARALLEL ALGORITHM FOR MATRIX MULTIPLICATION BY GRAMIAN OF TOEPLITZ--BLOCK MATRIX. Technical Reports. NATO/977203/3. Slovak Academy of Sciences, Bratislava, Slovakia. 32 pages.
  • Björck, Åke; Heggernes, Pinar; Matstoms, Pontus. 1999. Methods for large scale total least square problems. Reports in Informatics. 167. Institutt for Informatikk, Universitetet i Bergen, Bergen. 20 pages.
  • Heggernes, Pinar; Matstoms, Pontus. 1998. Partitioning a Set of Functions into Correlated Subsets. VTI rapport. 416A. Swedish National Road and Transport Research Institute (VTI). 36 pages.
  • Blair, Jean R. S.; Heggernes, Pinar; Telle, Jan Arne. 1996. Making an arbitrary filled graph minimal by removing fill edges. Reports in Informatics. 115. Institutt for Informatikk, UiB. 14 pages.
  • Heggernes, Pinar. 1996. Partitioning and ordering graphs for sparse matrix computations. Institutt for Informatikk. 144 pages.
  • Heggernes, Pinar; Matstoms, Pontus. 1996. Finding good column orderings for sparse QR factorization. Reports in Informatics. 120. Institutt for Informatikk, UiB.
  • Heggernes, Pinar; Matstoms, Pontus. 1996. Finding Good Column Orderings for Sparse QR Factorization. Reports in Informatics. 120. Institutt for Informatikk. 29 pages.
  • Heggernes, Pinar; Aspvall, Bengt; Telle, Jan Arne. 1995. A simple cubic algorithm for computing minimum height elimination trees for interval graphs. Reports in Informatics. 103. Institutt for informatikk, UiB-MatNat. 10 pages.
  • Heggernes, Pinar; Telle, Jan Arne. 1995. Partitioning Graphs Into Generalized Domination Sets. Reports in Informatics. 107. Institutt for informatikk, UiB-MatNat. 20 pages.
  • Aspvall, B.; Heggernes, Pinar. 1994. Finding Minimum Height Elimination Trees for Interval Graphs in Polynomial Time. Report in Informatics. 80. UiB-MatNat: Institutt for informatikk.
Book sections
  • Heggernes, Pinar; van 't Hof, Pim; Lokshtanov, Daniel; Paul, Christophe. 2011. Obtaining a bipartite graph by contracting few edges. Session 4A, pages 217-228. In:
    • Chakraborty, Supratik; Kumar, Amit. 2011. IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2011. 480 pages. ISBN: 9783939897347.
  • Heggernes, Pinar; Paul, Christophe; Telle, Jan Arne; Villanger, Yngve. 2007. Interval completion with few edges. 8B, pages 374-381. In:
    • Johnson, David; Feige, Uriel. 2007. STOC: Annual ACM Symposium on Theory of Computing. Association for Computing Machinery (ACM). 735 pages. ISBN: 978-1-59593-631-8.
  • Heggernes, Pinar; Telle, Jan Arne; Villanger, Yngve. 2005. Computing Minimal Triangulations in Time O(nα log n) = o(n2.376). Session 9C, pages 907-916. In:
    • Buchsbaum, Adam. 2005. Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005. Society for Industrial and Applied Mathematics. 1185 pages. ISBN: 0-89871-585-7.
  • Heggernes, Pinar; Moe, Richard Elling. 2002. Det profesjonsorienterte studiet i IKT. Forslag til undervisning og student-vurdering. 113-126. In:
    • Nordmo, Ivar. 2002. UPED-skrift 2/02 Bidrag fra deltakerne i uviklingsprogram i universitetspedagogikk.

More information in national current research information system (CRIStin)

All publications