Philip Klein - bibTex


@InProceedings{MultiwayCut2012,
  author =      {Mohammadhossein Bateni and Mohammadtaghi Hajiaghayi and Philip Klein and Claire Mathieu},
  title =      {A Polynomial-time Approximation Scheme for Planar Multiway Cut},
  booktitle = {Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms},
  year =      2012,
  note =      {to appear}}

@InProceedings{EfficientSteinerForestPTAS2011,
  author =      {David Eisenstat and Philip N. Klein and Claire Mathieu},
  title =      {An efficient polynomial-time approximation scheme for Steiner forest in planar graphs},
  booktitle = {Proceedings of the 23nd ACM-SIAM Symposium On Discrete Algorithms},
  year =      2012,
  note =      {to appear}}

 @InProceedings{MSMSflow2011,
  author =      {Glencora Borradaile and
               Philip N. Klein and
               Shay Mozes and
               Yahav Nussbaum and
               Christian Wulff-Nilsen},
  title =      {Multiple-Source Multiple-Sink Maximum Flow in Directed Planar
               Graphs in Near-Linear Time},
  booktitle = {Proceedings of the 52nd Annual IEEE Symposium on
 Foundations of Computer Science},
  year =      2011,
  note =      {to appear}}

@InProceedings{KKS2011,
  author =       {Ken-ichi Kawarabayashi and
               Philip N. Klein and
               Christian Sommer},
  title =        {Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus,
               and Minor-Free Graphs},
  booktitle = {Proceedings of the 38th International Colloquium on Automata, Languages and Programming, {ICALP} 2011},
  pages =     {135-146},
  year =      2011}

@InProceedings{KleinM11,
  author =      {Philip N. Klein and Shay Mozes},
  title =      {Multiple-Source Single-Sink Maximum Flow in Directed Planar Graphs in $O(\mbox{diameter }n \log n)$ Time},
  booktitle = {Proceedings of the 12th Algorithms and Data Structures Symposium, WADS 2011},
  year =      2011,
  pages = {571-582}}

@Article{BorradaileKleinMathieu2009,
  author =      {Glencora Borradaile and Philip N. Klein and Claire Mathieu},
  title =      {A polynomial-time approximation schee for Steiner tree in planar graphs},
  journal =      {ACM Transactions on Algorithms},
  year =      2009,
  volume =      5,
  note =      {Special Issue on SODA 2007}}

@InProceedings{DemaineHajiaghayiKlein2009,
  author =      {Erik D. Demaine and MohammadTaghi Hajiaghayi and Philip Klein},
  title =      {Node-weighted Steiner tree and group Steiner tree in planar graphs},
  booktitle = {Proceedings of the 36th International Colloquium on
Automata, Languages and Programming},
  year =      2009}

@Article{BorradaileKlein2009,
  author =      {Glencora Borradaile and  Philip N. Klein},
  title =      {An $O(n \log n)$ algorithm for maximum st-flow in a directed planar graph},
  journal =      {Journal of the ACM},
  year =      2009,
  volume =      56,
  number =      2}


@InProceedings{KleinMozesWeimann2009,
  author =      {Philip N. Klein and Shay Mozes and Oren Weimann},
  title =      {Shortest paths in directed planar graphs with negative lengths: a linear-space $O(n \log^2 n)$-time algorithm},
  booktitle = {Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms},
  pages =      {236-245},
  year =      2009}


@Article{KleinTSP2008,
  author =      {Philip N. Klein},
  title =      {A linear-time approximation scheme for TSP in undirected planar graphs with edge-weights},
  journal =      {SIAM Journal on Computing},
  year =      2008,
  volume =      37,
  number =      6,
  pages =      {1926-1952}}



@InProceedings{BorradaileKlein2008,
  author =      {Glencora Borradaile and Philip N. Klein},
  title =      {The two-edge connectivity survivable network problem in planar graphs},
  booktitle = {Proceedings of the 35th International Conference on Automata, Languages, and Programming},
  pages =      {485-501},
  year =      2008}



@InProceedings{BorradaileKleinMathieu2008,
  author =      {Glencora Borradaile, Philip N. Klein, and Claire Mathieu},
  title =      {A polynomial-time approximation scheme for Euclidean Steiner forest},
  booktitle = {Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science},
  pages =      {115-124},
  year =      2008}

@InProceedings{KleSteinerWADS2007,
  author =      {Glencora Borradaile and Philip N. Klein and Claire Mathieu},
  title =      {An $O(n \log n)$ approximation scheme with
singly-exponential dependence on epsilon},
  booktitle =      {Proceedings, 10th International Workshop on Algorithms and Data Structures},
  year =     2007,
  pages =     {275-286}
}


@InProceedings{KleSpanner2006,
  author = {Glencora Borradaile and Claire Kenyon-Mathieu and Philip N. Klein},
  title =      {A polynomial-time approximation scheme for Steiner tree in planar graphs},
  booktitle =      {Proceedings, 18th Annual ACM-SIAM Symposium on Discrete Algorithms},
  year =     2007,
  pages =     {1285-1294}
}

@InProceedings{KleSpanner2006,
  author =      {Philip N. Klein},
  title =      {A subset spanner for planar graphs, with application to subset TSP},
  booktitle =      {Proceedings, 38th ACM Symposium on Theory of Computing},
  year =     2006,
  pages =     {749-756}
}

@InProceedings{BorKle2006,
  author =      {Glencora Borradaile and Philip N. Klein},
  title =      {An $O(n \log n)$ algorithm for maximum $st$-flow in a directed planar graph},
  booktitle =      {Proceedings, 17th ACM-SIAM Symposium on Discrete Algorithms},
  pages =     {524-533},
  year =     2006
}

@Article{KleKriRagRav2004,
  author =      {Philip N. Klein and Radha Krishnan and Balaji Raghavachari and R. Ravi},
  title =      {Approximation through local optimality: designing networks with small degree},
  journal =      {Networks},
  year =      2004,
  volume =     44,
  pages =     {203-215}
}

@InProceedings{KleinTSP2005,
  author =      {Philip N. Klein},
  title =      {A linear-time approximation scheme for TSP for planar weighted graphs},
  booktitle =      {Proceedings, 46th IEEE Symposium on Foundations of Computer Science},
  pages =     {146-155},
  year =     2005
}

@Article{AKR1995,
  author =      {Ajit Agrawal and Philip N. Klein and R. Ravi},
  title =      { When trees collide: An approximation algorithm for the generalized Steiner tree problem on networks},
  journal =      {SIAM Journal on Computing},
  year =      1995,
  volume =     24,
  pages =     {440-456}
}

@Article{KRAR,
  author =      {Philip N. Klein and Satish Rao and Ajit Agrawal and and R. Ravi},
  title =      { An approximate max-flow min-cut relation for multicommodity flow, with applications},
  journal =      {Combinatorica},
  year =      1995,
  volume =     15,
  pages =     {187-202}
}

@Article{KlePloSteTar1994,
  author =      {Philip N. Klein and Serge Plotkin and Clifford Stein and Éva Tardos},
  title =      {Faster approximation algorithms for the unit capacity concurrent flow problem with applications to routing and finding sparse cuts},
  journal =      {SIAM Journal on Computing},
  year =      1994,
  volume =     23,
  pages =     {466-487}
}


@InProceedings{KleColTar1994,
  author =      {Philip N. Klein and Richard Cole and Robert E. Tarjan},
  title =      {A linear-work parallel algorithm for finding a minimum spanning tree},
  booktitle =      {Proceedings, 6th ACM Symposium on Parallel Algorithms and Architectures},
  pages =     {11-15},
  year =     1994
}

@Article{Klein1993,
  author =      {Philip N. Klein},
  title =      {Parallelism, preprocessing, and reachability: a hybrid algorithm for directed graphs},
  journal =      {Journal of Algorithms},
  year =      1993,
  volume =     14,
  pages =     {331-343}
}


@Article{KleSte1993,
  author =      {Philip N. Klein and Clifford Stein},
  title =      {A parallel algorithm for approximating the minimum cycle cover},
  journal =      {Algorithmica},
  year =      1993,
  volume =     9,
  pages =     {23-31}
}


@InProceedings{AKR1991,
  author =      {Ajit Agrawal and Philip N. Klein and R. Ravi},
  title =      {Ordering problems approximated: register sufficiency, single-processor scheduling and interval graph completion},
  booktitle =      {Proceedings, 18th International Conference on Automata, Languages, and Programming},
  pages =     {751-762},
  year =     1991
}

@Article{HelKleWil1990,
  author =      {Lisa Hellerstein and Philip N. Klein and Robert Wilber},
  title =      {On the time-space complexity of reachability queries for preprocessed graphs},
  journal =      {Information Processing Letters},
  year =      1990,
  volume =     34,
  pages =     {307-312}
}




@Article{SebKleKim2004,
author = "Thomas Sebastian, Philip N. Klein, and Benjamin Kimia",
title = "Recognition of shapes by editing their shock graphs",
journal = "IEEE Transactions on Pattern Analysis and Machine Intelligence",
pages="550-571",
volume = "26",

number = 5,
year = "2004",
}

@Article{KleLuNet03,
author = "Klein and Lu and Netzer",
title = "Detecting Race Conditions in Parallel Programs that
Use Semaphores",
journal = "Algorithmica",
pages="321-345",
volume = "35",
year = "2003",
}

@Article{KleinPAMI2003,
author = {T. B. Sebastian and P. N. Klein and B. B. Kimia},
title = {On aligning curves},
journal = {IEEE Transactions on Pattern Analysis and Machine Intelligence},
year = 2003,
volume = 25,
number = 1,
pages = {116-125}
}

@Article{Sebastian:2002:SBI,
author = "Thomas B. Sebastian and Philip N. Klein and Benjamin
B. Kimia",
title = "Shock-Based Indexing into Large Shape Databases",
journal = "Lecture Notes in Computer Science",
volume = "2352",
pages = "731-746",
year = "2002",
}

@Article{oai:arXiv.org:cs/0208004,
title = "Detecting Race Conditions in Parallel Programs that
Use Semaphores",
author = "Philip N. Klein and Hsueh-I Lu and Rob H. B. Netzer",
month = aug # "~03",
journal = "Algorithmica",
volume = "35",
pages = ":321-345"
year = "2003",
}

@InProceedings{SODA02*820,
author = "Philip N. Klein",
title = "Preprocessing an Undirected Planar Network to Enable Fast",
pages = "820--827",
booktitle = "Proceedings of the 13th Annual {ACM}-{SIAM} Symposium
On Discrete Mathematics ({SODA}-02)",
month = jan # " ~6--8",
publisher = "ACM Press",
address = "New York",
year = "2002",
}

@InProceedings{SODA01*781,
author = "Philip N. Klein and Thomas B. Sebastian and Benjamin
B. Kimia",
title = "Shape Matching using Edit-distance: An
Implementation",
pages = "781--790",
booktitle = "Proceedings of the Twelfth Annual {ACM}-{SIAM}
Symposium on Discrete Algorithms ({SODA}-01)",
month = jan # " ~7--9",
publisher = "ACM Press",
address = "New York",
year = "2001",
}

@Article{Sebastian:2001:ABR,
author = "Thomas B. Sebastian and Philip N. Klein and Benjamin
B. Kimia",
title = "Alignment-Based Recognition of Shape Outlines",
journal = "Lecture Notes in Computer Science",
volume = "2059",
pages = "606--618",
year = "2001",
}

@InProceedings{ICCV01-VOLI*755,
author = "Thomas Sebastian and Philip Klein and Benjamin Kimia",
title = "Recognition of Shapes by Editing Shock Graphs",
pages = "755--762",
booktitle = "Proceedings of the Eighth International Conference On
Computer Vision ({ICCV}-01)",
month = jul # " ~9--12",
publisher = "IEEE Computer Society",
address = "Los Alamitos, CA",
year = "2001",
}

@inproceedings{352627,
author = {Thomas W. Doeppner and Philip N. Klein and Andrew Koyfman},
title = {Using router stamping to identify the source of IP packets},
booktitle = {Proceedings of the 7th ACM conference on Computer and communications security},
year = {2000},
pages = {184--189},
publisher = {ACM Press},
}

@InProceedings{KleinImageAnalysis2000,
author = {J. Crisco and P. N. Klein and B. B. Kimia and T. B. Sebastian},
title = {Constructing 2D curve atlases},
booktitle ={Proceedings, IEEE Workshop on
Mathematical Methods in Biomedical Image Analysis},
pages = {70--77},
year = 2000
}

@InProceedings{KleinTirthapuraSODA2000,
author = {P. N. Klein and S. Tirthapura and D. Sharvit and B. B. Kimia},
title = {A tree-edit-distance algorithm for comparing simple, closed shapes},
booktitle ={Proc. ACM-SIAM Symposium on Discrete Algorithms},
pages = {696-704},
year = 2000
}

@inproceedings{338661,
author = {Philip Klein},
title = {Finding the closest lattice vector when it's unusually close},
booktitle = {Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms},
year = {2000},
isbn = {0-89871-453-2},
pages = {937--941},
location = {San Francisco, California, United States},
publisher = {Society for Industrial and Applied Mathematics},
}

@InProceedings{klein99acm,
author = {David R. Karger, Philip N. Klein, Cliff Stein, Mikkel Thorup, and Neal E. Young},
title = {Rounding algorithms for a geometric embedding relaxation of minimum multiway cut},
booktitle = {Proceedings, ACM Symposium on Theory of Computing},
pages = {668-678},
year = 1999,
}

@InProceedings{klein99number,
author = {Philip Klein and Neal Young},
title = {On the number of iterations for Dantzig-Wolfe optimization and packing-covering approximation algorithms},
booktitle = {Proceedings, Integer Programming and Combinatorial Optimization},
pages = {320-327},
year = 1999,
volume = 1610,
series = {Lecture Notes in Computer Science},
publisher = {Springer-Verlag}
}

@Article{KleSub98,
author = "Klein and Subramanian",
title = "A Fully Dynamic Approximation Scheme for Shortest
Paths in Planar Graphs",
journal = "Algorithmica",
volume = "22",
pages = "235-249",
year = "1998",
}

@InProceedings{KleinSPIE,
author = {S. Tirthapura and D. Sharvit and P. Klein and B. Kimia},
title = {Indexing based on edit-distance matching of shape graphs},
booktitle ={SPIE International Symposium on Voice, Video, and Data Communications},
pages = {25--36},
year = 1998
}

@Article{Klein:1998:SEA,
author = "Philip N. Klein and Hsueh-I Lu",
title = "Space-Efficient Approximation Algorithms for {MAXCUT}
and {COLORING} Semidefinite Programs",
journal = "Lecture Notes in Computer Science",
volume = "1533",
pages = "387--396",
year = "1998",
}

@inproceedings{
author = "Philip N. Klein",
title = "Computing the Edit-Distance between Unrooted Ordered Trees",
journal = "European Symposium on Algorithms",
pages = "91-102",
year = "1998",
}

@inproceedings{ arora98polynomialtime,
author = "Sanjeev Arora and Michelangelo Grigni and David R. Karger and Philip N. Klein and Andrzej Woloszyn",
title = "A polynomial-time approximation scheme for weighted planar graph TSP",
booktitle = "Symposium on Discrete Algorithms",
pages = "33-41",
year = "1998",
}

@article{
author = {Philip N. Klein, Serge A. Plotkin, Satish Rao, Éva Tardos",
title = "Approximation Algorithms for Steiner and Directed Multicuts",
journal = "Journal of Algorithms",
pages = "241-269",
year = "1997",
}

@Article{HenzingerKRS,
author = {M. R. Henzinger and P. N. Klein and S. Rao and S. Subramanian},
title = {Faster shortest-path algorithms for planar graphs},
journal = {Journal Comp. Sys. Sci.},
year = 1997,
volume = 55,
number = 1,
pages = {3-23}
}

@article{
author = "Philip N. Klein, Sairam Subramanian",
title = "A Randomized Parallel Algorithm for Single-Source Shortest Paths",
journal = "Journal of Algorithms",
year = 1997,
volume = 25,
pages = "205-220",
}

@Article{SICOMP::Klein1996,
title = "Efficient Parallel Algorithms for Chordal Graphs",
author = "Philip N. Klein",
pages = "797--827",
journal = "SIAM Journal on Computing",
month = aug,
year = "1996",
volume = "25",
number = "4",
}

@InProceedings{STOC96*338,
author = "Philip Klein and Hsueh-I. Lu",
title = "Efficient approximation algorithms semidefinite
programs arising from max-cut and coloring",
pages = "338--347",
booktitle = "Proceedings of The Twenty-Eighth Annual {ACM}
Symposium On The Theory Of Computing ({STOC} '96)",
ISBN = "0-89791-785-5",
month = may,
publisher = "ACM Press",
address = "New York, USA",
year = "1996",
}

@InProceedings{ESA::KleinLN1996,
title = "Race-Condition Detection in Parallel Computation with
Semaphores (Extended Abstract)",
author = "Philip N. Klein and Hsueh-I Lu and Robert H. B.
Netzer",
booktitle = "Algorithms---{ESA}~'96, Fourth Annual European
Symposium",
editor = "Josep D{\'\i}az and Maria Serna",
address = "Barcelona, Spain",
month = "25--27~" # sep,
year = "1996",
series = "Lecture Notes in Computer Science",
volume = "1136",
publisher = "Springer",
ISBN = "ISBN 3-540-61680-2",
pages = "445--459",
}

@inProceedings{
title = "Finding Minimum Spanning Forests in Logarithmic Time and Linear Work Using Random Sampling",
author = "Richard Cole, Philip N. Klein, Robert Endre Tarjan",
journal = "Symposium on Parallel Algorithms and Architecture",
year = "1996",
pages = "243-250",
}

@Article{
author = "David R. Karger, Philip N. Klein, Robert Endre Tarjan",
title = "A Randomized Linear-Time Algorithm to Find Minimum Spanning Trees"
journal = "Journal of the ACM",
year = "1995",
volume = "42",
pages = "321-328",
}

@Article{JALGO::KleinR1995,
title = "A Nearly Best-Possible Approximation Algorithm for
Node-Weighted {Steiner} Trees",
author = "Philip Klein and R. Ravi",
pages = "104--115",
journal = "Journal of Algorithms",
year = "1995",
month = jul,
volume = "19",
number = "1",
}

@Article{Klein:1994:DSB,
author = "Philip N. Klein",
title = "A data structure for bicategories, with application to
speeding up an approximation algorithm",
journal = "Information Processing Letters",
volume = "52",
number = "6",
pages = "303--307",
day = "23",
month = dec,
year = "1994",
}

@InProceedings{Klein93,
author = "Philip Klein",
title = "On {G}azit and {M}iller's Parallel Algorithm for
Planar Separators: Achieving Greater Efficiency through
Random Sampling",
booktitle = "Proceedings of the 5th Annual {ACM} Symposium on
Parallel Algorithms and Architectures",
address = "Velen, Germany",
organization = "SIGACT and SIGARCH",
month = jun # " 30--" # jul # " 2,",
year = "1993",
pages = "43--49",
}

@Article{KaoK93,
title={Towards Overcoming the Transitive-Closure Bottleneck: Efficient
Parallel Algorithms for Planar Digraphs},
author={Ming-Yang Kao and Philip N. Klein},
pages={459--500},
journal=jcss,
year=1993,
month=dec,
volume=47,
number=3,
}

@Article{KNK,
author = {S. Khuller and J. Naor and P. Klein},
title = {The Lattice Structure of Flow in Planar Graphs},
journal = {SIAM J. Discrete Math},
year = 1993,
volume = 6,
number = 3,
pages = {477-490}
}

@InProceedings{Klein:1993:EMN,
author = "Philip Klein and Serge A. Plotkin and Satish Rao",
title = "Excluded minors, network decomposition, and
multicommodity flow",
booktitle ={ACM Symposium on Theory of Computing},
pages = "682--690",
year = 1993,
bibdate = "Wed Feb 20 18:34:01 MST 2002",
bibsource = "http://portal.acm.org/",
}

@Conference{aug:KleinRavi:93,
author = "Philip Klein and R. Ravi",
title = "When Cycles Collapse: {A} General Approximation
Technique for Constraind Two-Connectivity Problems",
booktitle = "Third IPCO Conference",
year = "1993",
editor = "G. Rinaldi and L. Wolsey",
page = "39--55",
}

@Article{KleinR88,
title={An Efficient Parallel Algorithm for Planarity},
author={Philip N. Klein and John H. Reif},
pages={190--246},
journal=jcss,
year=1988,
month=oct,
volume=37,
number=2,
references={}
}